글 읽기 - 테스트 케이스는 모두 통과인데 왜 틀렸을까요..

smhan213 2년 전 0

안녕하세요, 테스트 케이스는 모두 통과했는데 왜 틀렸을까요..

DFS를 통해 트리의 깊이를 탐색하고 LCA를 이용했습니다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_NUM 100001

int visited[MAX_NUM];
int depth[MAX_NUM];
int dp[20][MAX_NUM]; // 10만은 2의 17제곱 보다 작으므로 행의 개수를 20까지 하면 충분하다.
int dpMin[20][MAX_NUM]; // 10만은 2의 17제곱 보다 작으므로 행의 개수를 20까지 하면 충분하다.
int dpMax[20][MAX_NUM]; // 10만은 2의 17제곱 보다 작으므로 행의 개수를 20까지 하면 충분하다.

typedef struct node{
    int x;
    int len;
    struct node* next;
}Node;

typedef struct{
    Node graph[MAX_NUM];
}Graph;


int min(int a, int b)
{
    if(a>b)
        return b;
    return a;
}

int max(int a, int b)
{
    if(a>b)
        return a;
    return b;
}


void Insert(Graph* pgraph, int a, int b, int c)
{
    Node* item1=(Node*)malloc(sizeof(Node));
    Node* item2=(Node*)malloc(sizeof(Node));
    Node* tmp;
    item1->len=c; item1->x=b; item1->next=NULL;
    item2->len=c; item2->x=a; item2->next=NULL;

    tmp=&pgraph->graph[a];
    while(tmp->next!=NULL)
        tmp=tmp->next;
    tmp->next=item1;

    tmp=&pgraph->graph[b];
    while(tmp->next!=NULL)
        tmp=tmp->next;
    tmp->next=item2;
}

void dfs(Graph* pgraph, int n, int d){
    visited[n]=1;
    depth[n]=d;
    Node* tmp=pgraph->graph[n].next;
    while(tmp!=NULL){
        if(visited[tmp->x]==0){
            visited[tmp->x]=1;
            dp[0][tmp->x]=n;
            dpMin[0][tmp->x]=tmp->len;
            dpMax[0][tmp->x]=tmp->len;
            dfs(pgraph, tmp->x, d+1);
        }
        tmp=tmp->next;
    }
    return;
}

void DP(int city_num){
    for(int i=1;i<20;i++){
        for(int j=1;j<=city_num;j++){
            dpMin[i][j]=min(dpMin[i-1][j], dpMin[i-1][dp[i-1][j]]);
            dpMax[i][j]=max(dpMax[i-1][j], dpMax[i-1][dp[i-1][j]]);
            dp[i][j]=dp[i-1][dp[i-1][j]];
        }
    }
}

int result[2]={0,987654321}; // {longest, shortest}
void lca(int x, int y)
{
    if(depth[x]!=depth[y]){
        if(depth[x]>depth[y]){
            /*swap*/
            int tmp=x;
            x=y;
            y=tmp;
        }
        for(int i=20; i>=0; i--){
            if(depth[y] - depth[x] >= 1<<i){
                result[0]=max(dpMax[i][y],result[0]);
                result[1]=min(dpMin[i][y],result[1]);
                y=dp[i][y];
            }
        }
    }

    if(x!=y){
        for(int i=20;i>=0;i--){
            if(dp[i][x]!=dp[i][y]){
                result[0]=max(result[0],dpMax[i][x]);
                result[1]=min(result[1],dpMin[i][x]);
                x=dp[i][x];

                result[0]=max(result[0],dpMax[i][y]);
                result[1]=min(result[1],dpMin[i][y]);
                y=dp[i][y];
            }
        }

        //둘이 서로 다르지만 dp[0]까지 모두 같을 수 있다. level=1인 두 노드인 경우, dp[0][x]=dp[0][y]=root 이므로 바로 그렇다.
        //이 경우 위의 반복문에서 최신화가 안되므로 longest와 shortest를 한번 최신화 해주어야 한다.
        result[0]=max(result[0],dpMax[0][x]);
        result[1]=min(result[1],dpMin[0][x]);
        result[0]=max(result[0],dpMax[0][y]);
        result[1]=min(result[1],dpMin[0][y]);        
    }
    
    return;
}

int main()
{
    Graph graph;
    int N, K, x, y;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        graph.graph[i].next=NULL;

    int a, b, c;
    int* LongShort;
    for(int i=1;i<N;i++){
        scanf("%d %d %d",&a,&b,&c);
        Insert(&graph,a,b,c);
    }

    dfs(&graph,1,0);
    DP(N);

    scanf("%d",&K);
    for(int i=0;i<K;i++){
        scanf("%d %d",&x,&y);
        lca(x,y);
        printf("%d %d\n",result[1],result[0]);
        result[0]=0; result[1]=987654321;
    }
}

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

문제

문제

출처

ICPC

테스트 케이스는 모두 통과인데 왜 틀렸을까요..

smhan213 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말