글 읽기 - 틀렸습니다! 반례좀 찾아주세요!! 부탁드립니다.

ksgkms23 5년 전 0

틀렸습니다! 가 뜹니다.

LCA알고리즘 이용하여 풀었습니다. 거의 비슷한 코드로 LCA 1,2를 풀었고 테스트 케이스또한 모두 맞습니다. 따로 만들었을 때도 잘 돌아갔습니다.

아무리 봐도 뭐가 틀린지 모르겠습니다, ㅜㅜ 반례가있을까요????

#include <vector>
#include <algorithm>
#include <iostream>
#define NMAX 40001
using namespace std;
vector<vector<pair<int,int>>> v;
int ac[NMAX][20];
int depth[NMAX];
bool visited[NMAX];
int dist[NMAX];
void getNode(int i){
    for(int j=0; j<v[i].size(); j++){
        if(visited[v[i][j].first]==false){
            depth[v[i][j].first] = depth[i]+1;
            dist[v[i][j].first] = v[i][j].second + dist[i];
            ac[v[i][j].first][0] = i;
            visited[v[i][j].first]=true;
            getNode(v[i][j].first);
        }
    }
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    v.resize(N+1);
    for(int i=0; i<N-1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    depth[1] = 1;
    visited[1] = true;
    getNode(1);
    for(int i=1; i<=N; i++)
        for(int j=0; j<19; j++){
            ac[i][j+1] = ac[ac[i][j]][j];
        }
    int M;
    cin >> M;
    while(M--){
        int a, b;
        int bottom, top;
        int par;
        cin >> a >> b;
        if(depth[a]>depth[b]){
            bottom = a;
            top = b;
        }
        else{
            bottom = b;
            top = a;
        }
        int diff;
        diff = depth[bottom] - depth[top];
        for(int i=0; diff; i++){
            if(diff%2==1){
                bottom = ac[bottom][i];
            }
            diff /= 2;
        }
        if(bottom==top){
            // 같은경우
            par = bottom;
            cout << dist[a]+dist[b]-(2*dist[par]) << '\n';
        }
        else{
            for(int i=19; i>=0; i--){
                if(ac[bottom][i]!=0 && ac[bottom][i]!=ac[top][i]){
                    bottom = ac[bottom][i];
                    top = ac[top][i];
                    break;
                }
            }
            par = ac[top][0];
            cout << dist[a]+dist[b]-(2*dist[par]) << '\n';
        }
    }
}

djm03178 5년 전 1

두 가지가 틀렸습니다.

37번째 38분째 줄이 서로 뒤바뀌어야 합니다. 자신의 2^j번째 조상의 2^j번째 조상을 구하지 않았는데 자신의 2^(j+1)번째 조상을 구할 수 있을까요?
74번째 줄을 지워야 합니다.

ksgkms23 5년 전 0

정말 감사드립니다. LCA 37 , 38번 라인을 확실히 이해하지 못하고 풀었었나봅니다. 마찬가지로 74번라인도 감사드립니다!

plum 5년 전 0

저 혹시 74번 라인은 왜 지워야되는건가요?

제 생각에는 답이 구해졌으니까 break하면 될 것 같은데 그렇게하면 안되는 이유가 무엇인가요?..ㅠㅠ

저도 계속 오류나다가 이글 참고해서 제 소스코드 부분에서 break지우니까 됫는데.. break를 왜 지워야하는지 아직 모르겠습니다ㅠㅠ

저 for문의 역할은 두 노드가 서로 공통 조상을 만나기 직전(그 조상의 자식)까지 포인터를 위로 올리는 것입니다. 예를 들어 어떤 노드의 6번째 조상이 LCA라면, 위로 4칸, 1칸을 차례차례 올라가야 바로 아래까지 도달할 텐데, 저기에 break가 있으면 4칸만 올라가고 멈추기 때문에 아직 LCA는 2칸 위에 있는 상황이 됩니다. 물론 우리는 여기서 LCA가 6번째 조상이라는 것을 이미 가정한 상황이지만 프로그램이 그것을 깨달으려면 저 for문 전체를 돌아야만 합니다.

plum 5년 전 0

@djm03178

헉 감사합니다 계속 고민했었는데 이렇게 명쾌히알려주셔서 감사합니다 복받으세요!!1

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

문제

문제

출처

ICPC

틀렸습니다! 반례좀 찾아주세요!! 부탁드립니다.

ksgkms23 5년 전 0

djm03178 5년 전 1

ksgkms23 5년 전 0

plum 5년 전 0

djm03178 5년 전 0

plum 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말