글 읽기 - [c++] 도저히 어느부분이 문제인지 모르겠습니다. 도와주세요ㅠㅠ

tizm423 3년 전 0

어느부분에서 문제가 있는지 모르겠습니다..ㅠㅠ

dfs를 돌리면서 1번노드로부터의 거리를 모두 저장하고, 이를 통해 두 정점의 거리를 찾습니다.

lca를 찾고 이를 통해 k번째 노드를 찾았습니다..

혹시 제 생각과는 다르게 코드가 짜여있나요??

알려주시면 감사하겠습니다ㅠㅠ

#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 100001;

vector<pair<int, int>> child[MAX_N];
long long cost[MAX_N];
int ST[20][MAX_N];
int depth[MAX_N];
bool visited[MAX_N];

void dfs(int node, int d, long long c) {
    visited[node] = true;
    depth[node] = d;
    cost[node] = c;
    int N = child[node].size();
    for(int i=0; i<N; i++){
        int nextNode = child[node][i].first;
        if(!visited[nextNode]){
            int nodeCost = child[node][i].second;
            ST[0][nextNode] = node;
            dfs(nextNode, d+1, c+nodeCost);
        }
    }
}

void buildST(int N){
    for(int i=1; i<20; i++){
        for(int j=1; j<=N; j++){
            ST[i][j] = ST[i-1][ST[i-1][j]];
        }
    }
}

int getLCA(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for(int i=0; diff; i++, diff >>= 1){
        if(diff&1) u = ST[i][u];
    }

    if(u!=v){
        for(int i=19; i>-1; i--){
            if(ST[i][u] != ST[i][v]){
                u = ST[i][u];
                v = ST[i][v];
            }
        }
        u = ST[0][u];
    }
    return u;
}

int getKthNode(int u, int v, int k){
    int lcaNode = getLCA(u, v);
    int leftDepthDiff = depth[u] - depth[lcaNode];
    int rightDepthDiff = depth[v] - depth[lcaNode];

    // lcaNode보다 왼쪽이라면
    if(k <= leftDepthDiff+1){
        int diff = k-1;
        for(int i=0; diff; i++, diff >>= 1){
            if(diff&1) u = ST[i][u];
        }
        return u;
    }else { // lcaNode보다 오른쪽이라면
        int diff = rightDepthDiff - (k - leftDepthDiff - 1);
        for(int i=0; diff; diff >>= 1){
            if(diff&1) v = ST[i][v];
        }
        return v;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;
    for(int i=1; i<N; i++){
        int a, b, c;
        cin >> a >> b >> c;
        child[a].push_back({b, c});
        child[b].push_back({a, c});
    }

    dfs(1, 0, 0);
    buildST(N);

    int M;
    cin >> M;
    while(M--){
        int command;
        cin >> command;
        if(command == 1){
            int u, v;
            cin >> u >> v;
            cout << cost[u]+cost[v] - cost[getLCA(u, v)]*2 << "\n";
        } else if(command == 2){
            int u, v, k;
            cin >> u >> v >> k;
            cout << getKthNode(u, v, k) << "\n";
        }
    }
}

tizm423 3년 전 0

69번째 for문안에 i++를 안 넣어서 틀렸었습니다.

부끄럽습니다..

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

문제

문제

출처

ICPC

[c++] 도저히 어느부분이 문제인지 모르겠습니다. 도와주세요ㅠㅠ

tizm423 3년 전 0

tizm423 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말