글 읽기 - 4% 런타임 에러

smoh1225 5년 전 0

어떤 노드의 왼쪽 브랜치의 길이와 오른쪽 브랜치의 길이의 합이 최대인 것을 그 노드에서의 지름이라고 합니다.

아무거나 루트가 될 수 있는(간선이 2개 이하인) 노드를 찾아서,

밑으로 내려가면서 각 노드에서의 지름을 구하고,

이중 최대를 전체 트리의 지름이라고 합니다.

4%에서 런타임 에러가 나는데 무엇이 문제인지 모르겠습니다.

#include <iostream>
#include <vector>

using namespace std;
typedef vector<vector<pair<int, int> > > G;


void printG(G& g){
    int n = g.size();
    for(int i=1; i<n; ++i){
        printf("%d: ", i);
        for(auto p : g[i]){
            printf("(%d, %d) ", p.first, p.second);
        }
        printf("\n");
    }
}

G getInput(){
    int n;
    scanf("%d", &n);
    G g(n+1, vector<pair<int, int> >());
    for(int i=0; i<n; ++i){
        int r;
        scanf("%d", &r);
        int v, w;
        scanf("%d", &v);
        while(v > 0){
            scanf("%d", &w);
            g[r].push_back({v, w});
            scanf("%d", &v);
        }
    }
    return g;
}

int setMaxDiameter(G& g, int r, int& m, vector<bool>& visited){
    //printf("root: %d\n", r);
    int l[2] = {0, 0};
    int i=0;
    for(auto e : g[r]){
        int v = e.first;
        int w = e.second;
        if(visited[v]) continue;
        //printf("v: %d\n", v);
        visited[v] = true;
        l[i++] = w + setMaxDiameter(g, v, m, visited);
    }
    int diameter = l[0] + l[1];
    if(diameter > m) m = diameter;
    //printf("%d: %d %d\n", r, l[0], l[1]);
    return max(l[0], l[1]);
}

int findRoot(G& g){
    int size = g.size();
    int i=0;
    for(i=1; i<size; ++i){
        if(g[i].size() < 3) break;
    }
    return i;
}

int solve(G &g){
    int size = g.size();
    int m = -1;
    vector<bool> visited(size, false);
    int r = findRoot(g);
    visited[r] = true;
    setMaxDiameter(g, r, m, visited);
    return m;
}

int main(){
    G g = getInput();
    //printG(g);
    int ans = solve(g);
    printf("%d\n", ans);

    return 0;
}

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

문제

문제

출처

ICPC

4% 런타임 에러

smoh1225 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말