글 읽기 - c++ 런타임에러

dreamian 6년 전 0

계속해서 런타임 에러가 뜨는데 어떤 점이 잘못됐을까요?

구현은,

1. 각 노드의 트리 구성

2. level 계산

3. 중위 순회를 하며 각 level의 너비 탐색

4. 최대 너비를 갖는 레벨과 그 너비 출력

이러한 방식으로 구현했습니다.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define node_num(i) candid.first
#define dir(i) candid.second

struct N{
    int parent;
    int left;
    int right;
    int level;
    int l_sz;
    int r_sz;
    int idx;
    // 구조체 초기화
    N() : parent(-1), left(-1), right(-1), level(-1), l_sz(0), r_sz(0), idx(0) {}
};

deque <int> query;

int lv_max=0;

void Init_lv(vector<N> &node, int root, int lv){
    lv_max=lv;
    node[root].level=lv;
    if(node[root].left!=-1) Init_lv(node,node[root].left,lv+1);
    if(node[root].right!=-1) Init_lv(node,node[root].right,lv+1);

    if(node[root].left==-1 && node[root].right==-1) query.push_back(root);
}

void inorder(vector<N> &node,int root, vector< pair<int,int> > &ans,int indi){

    int cmp;
    if(node[root].left!=-1){
        indi-=node[node[root].left].r_sz+1;
        node[node[root].left].idx+=indi;
        cmp=ans[node[node[root].left].level].first;
        ans[node[node[root].left].level].first=cmp<node[node[root].left].idx?cmp:node[node[root].left].idx;
        inorder(node,node[root].left,ans,indi);
        indi+=node[node[root].left].r_sz+1;
    }
    cmp=ans[node[root].level].first;
    ans[node[root].level].first=cmp<node[root].idx?cmp:node[root].idx;
    cmp=ans[node[root].level].second;
    ans[node[root].level].second=cmp>node[root].idx?cmp:node[root].idx;
        
    if(node[root].right!=-1){
        indi+=node[node[root].right].l_sz+1;
        node[node[root].right].idx+=indi;
        cmp=ans[node[node[root].right].level].second;
        ans[node[node[root].right].level].second=cmp>node[node[root].right].idx?cmp:node[node[root].right].idx;
        inorder(node,node[root].right,ans,indi);
    }

}

int main(){
    int n;
    scanf("%d",&n);
    vector<N> node(n+1);
    for(int i=0;i<n;i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        node[a].left=b;
        if(b!=-1) node[b].parent=a;
        node[a].right=c;
        if(c!=-1) node[c].parent=a;
    }
    int root;
    for(int i=1;i<=n;i++){
        if(node[i].parent!=-1) continue;
        Init_lv(node,i,1);
        root=i;
        break;
    }

    while(!query.empty()){
        int a=query.front();
        query.pop_front();
        if(node[a].parent==-1) continue;

        if(node[node[a].parent].left==a){
            node[node[a].parent].l_sz=node[a].l_sz+node[a].r_sz+1;
        }
        else node[node[a].parent].r_sz=node[a].l_sz+node[a].r_sz+1;
        
        if(query.back()==node[a].parent) continue;
        query.push_back(node[a].parent);
    }
    
    vector< pair<int,int> > ans(lv_max+1,make_pair(1e+9,-1e+9));
    inorder(node,root,ans,0);
    pair<int,int> anss(make_pair(0,0));
    for(int i=1;i<=lv_max;i++){
        if(anss.second<ans[i].second-ans[i].first+1){
            anss.second=ans[i].second-ans[i].first+1;
            anss.first=i;
        }
    }

    printf("%d %d\n",anss.first,anss.second);

    return 0;
}

dreamian 6년 전 2

25번째 line을 lv_max=lv_max>lv?lv_max:lv; 로 수정해주어 AC 받았습니다.

[반례]

14
1 2 3
2 4 -1
3 7 -1
4 5 6
7 9 8
8 -1 -1
9 14 -1
14 13 -1
13 -1 12
12 11 -1
11 10 -1
10 -1 -1
5 -1 -1
6 -1 -1

-> 4 13

각 level의 너비를 출력했을 시에 lv_max가 4에서 끊김.

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

문제

문제

출처

ICPC

c++ 런타임에러

dreamian 6년 전 0

dreamian 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말