글 읽기 - 3176번 질문입니다 LCA 문제입니다.

resolution15 6년 전 0

parent를 dp로 만들면서 least와 largest를 채워나가며

lca를 찾을때도 parent를 찾으면서 계산하는 방법을 이용했습니다.

예제는 통과하는데 무엇이 잘못되었을까요..

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;

const int MAX = 100001;
vector < pair < int , int > > v[MAX];
// v[a] = (b,c)    a->b 로 cost : c
int depth[MAX];
int parent[MAX][18];
int least[MAX][18];
int largest[MAX][18];
void make_parent_by_DFS(int cur){
    for(int i=0; i<v[cur].size(); i++){
        int next = v[cur][i].first;
        if(depth[next] == -1){
            depth[next] = depth[cur]+1;
            parent[next][0] = cur;
            least[next][0]=v[cur][i].second;
            largest[next][0]=v[cur][i].second;
            make_parent_by_DFS(next);
        }
    }
}
void query(int d,int e){
    int ans_largest=-1;
    int ans_least=1000001;
    int u=d;
    int v=e;
    if(depth[u] < depth[v])
        swap(u,v);
    int diff = depth[u]-depth[v];
    for(int i=0; diff; i++){
        if(diff%2){
            ans_least = min(ans_least,least[u][i]);
            ans_largest = max(ans_largest,largest[u][i]);
            u= parent[u][i];
        }
        diff/=2;
    }
    if(u != v){
        for(int j = 18-1; j>=0; --j){
            if(parent[u][j] != -1 && parent[u][j] != parent[v][j]){
                u=parent[u][j];
                v=parent[v][j];
                ans_least = min(ans_least, min(least[u][j],least[v][j]));
                ans_largest = max(ans_largest,max(largest[u][j],largest[v][j]));
            }
        }
        ans_least = min(ans_least,min(least[u][0],least[v][0]));
        ans_largest = max(ans_largest,max(largest[u][0],largest[v][0]));
    }
    printf("%d %d\n",ans_least, ans_largest);
}
int main(){
    memset(parent,-1,sizeof(parent));
    memset(depth,-1,sizeof(depth));
    for(int i=0; i<MAX; i++){
        for(int j=0; j<18; j++)
            least[i][j]=1000001;
    }
    memset(largest,-1,sizeof(largest));
    int n,k;
    cin >> n;
    for(int i=0; i<n-1; i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    depth[1]=0;
    make_parent_by_DFS(1);
    for(int j=0; j<18-1; ++j){
        for(int i=1; i<n; ++i){
            if(parent[i][j] != -1){
                parent[i][j+1] = parent[parent[i][j]][j];
                least[i][j+1] = min(least[i][j],least[parent[i][j]][j]);
                largest[i][j+1] = max(largest[i][j],largest[parent[i][j]][j]);

            }
        }
    }
    cin >> k;
    for(int i=0; i<k; i++){
        int d,e;
        scanf("%d %d",&d,&e);
        query(d,e);
    }

}

popuur 5년 전 0

u,v 가 바뀐채로 들어가서 값이 변경되는거같습니다.

//as-is
if(u != v){
        for(int j = 18-1; j>=0; --j){
            if(parent[u][j] != -1 && parent[u][j] != parent[v][j]){
                u=parent[u][j];
                v=parent[v][j];
                ans_least = min(ans_least, min(least[u][j],least[v][j]));
                ans_largest = max(ans_largest,max(largest[u][j],largest[v][j]));
            }
        }
        ans_least = min(ans_least,min(least[u][0],least[v][0]));
        ans_largest = max(ans_largest,max(largest[u][0],largest[v][0]));
    }

//to-be
if(u != v){
        for(int j = 18-1; j>=0; --j){
            if(parent[u][j] != -1 && parent[u][j] != parent[v][j]){
               //순서변경
               ans_least = min(ans_least, min(least[u][j],least[v][j]));
               ans_largest = max(ans_largest,max(largest[u][j],largest[v][j]));
               u=parent[u][j];
               v=parent[v][j]; 
            }
        }
        ans_least = min(ans_least,min(least[u][0],least[v][0]));
        ans_largest = max(ans_largest,max(largest[u][0],largest[v][0]));
    }

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

문제

문제

출처

ICPC

3176번 질문입니다 LCA 문제입니다.

resolution15 6년 전 0

popuur 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말