글 읽기 - 밑에 yoonjong1820님이 올리신 코드에 의문이 있습니다.

wnsdl1659 3년 전 0

이 코드로 yoonjong1820 님이 맞았다고 뜨는데

밑에 올린 테스트 케이스로는 시간초과가 나와야하는게 아닌가 싶습니다.

이 테스트 케이스는 1을 기준으로 양 옆으로 약 25000개씩 시옷 모양으로 길게 생긴 트리입니다.

그리고 양 옆 맨 밑의 노드를 두개의 최소 공통 조상을 찾는 케이스 입니다.

확인 부탁드립니다.

#include <iostream>
#include <deque>
#include <queue>
#include <string>
#include <vector>
using namespace std;

vector<int> tree[50001];
int parent[50001];
bool check[50001];

void findfirstParent(int n) {              // n은 시작 노드
    check[n] = true;

    for (int i = 0; i < tree[n].size(); i++) {
        int idx = tree[n][i];       
        if (check[idx] == true) continue;
        parent[idx] = n; 
        findfirstParent(idx);
    }
}


void common(int a, int b) { 
    // a와 b가 같을 경우
    if (a == b) {
        cout << a << endl;
        return;
    }
    // 다르다면
    else {
        int aAnc = a;   // ancestor of a
        int bAnc;       // ancestor of b
        int count1 = 0; // a를 일단 고정후 b를 전체 탐색했을 때 탐색개수 카운트
        int mem1 = -1;  // 조상을 탐색하여 답을 찾았을 때 그 노드값을 저장하는 변수
        bool isfound = false;
        while (!isfound) { // a 조상 탐색
            bAnc = b;
          
            if (aAnc == bAnc) {
                mem1 = bAnc;
                isfound = true;
            }

            while (!isfound && bAnc != 1) { // b조상 탐색
                bAnc = parent[bAnc];
                count1++;
                if (aAnc == bAnc) {
                    mem1 = bAnc;
                    isfound = true;
                }
            }
            if (aAnc == 1) break;
            aAnc = parent[aAnc];
            count1++;

        }



        bAnc = b;
        int count2 = 0; // b를 일단 고정후 a를 전체 탐색
        int mem2 = -1;
        isfound = false;
        while (!isfound) { // b 조상 탐색
            aAnc = a;
            
            if (aAnc == bAnc) {
                mem2 = aAnc;
                isfound = true;

            }


            while (!isfound && aAnc != 1) { // a 조상 탐색
                aAnc = parent[aAnc];
                count2++;
                if (aAnc == bAnc) {
                    mem2 = aAnc;
                    isfound = true;
                }
            }

            if (bAnc == 1) break;
            bAnc = parent[bAnc];
            count2++;

        }

        if (mem1 == -1 || mem2 == -1) { 
            if (mem1 == -1) cout << mem2 << endl;
            else cout << mem1 << endl;
        }
        else { //카운트가 최소가 되는 노드를 출력해야 함.
            if (count1 < count2) cout << mem1 << endl;
            else cout << mem2 << endl;
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    findfirstParent(1);

    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        common(a, b);
    }

}

wider93 3년 전 0

test.txt가 안 열리네요... 그리고 저격되는 게 맞는 것 같다면 그냥 요청에 테케추가 올리시는 게 좋을 것 같네요

wnsdl1659 3년 전 0

네 감사합니다. 혹시 제가 잘못 알고 있는 것일가 생각되어 확실하지 않아 질문으로 먼저 올렸습니다.

wider93 3년 전 0

입력이 문제의 조건에 맞고, 타겟으로 삼는 소스가 있고, 로컬에서 릴리즈 모드로 실행해서 그 소스가 시간 초과 떴으면 그걸로 충분하다고 생각합니다.

런타임 에러나 메모리 초과라면야 빌드 옵션에 따라 좀 다를 수도 있지만요. 실제로 데이터가 약한 것 같으니 추가요청 하시면 될 것 같습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

밑에 yoonjong1820님이 올리신 코드에 의문이 있습니다.

wnsdl1659 3년 전 0

wider93 3년 전 0

wnsdl1659 3년 전 0

wider93 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말