Submission #218081

#	Time	Username	Problem	Language	Result	Execution time	Memory
218081		brainwarego	트리 (KOI16_tree)	C++14	100 / 100	307 ms	16376 KiB

tree

#include <stdio.h>
#define LM 200010
 
int N, Q, par[LM], group[LM], gn;
int used[LM], gtop[LM] = {1};
struct Node{
    int node;
    Node*next;
}adj[LM], buf[LM*3];
int bCnt;
 
struct Queue{
    Node*now;
    Node* hasNext(){
        while(now->next && used[now->next->node]){
            now->next = now->next->next;
        }
        now = now->next;
        return now;
    }
}xQue[LM], yQue[LM];
int xf, xe, yf, ye;
 
void push_adj(int s, int e){
    buf[bCnt] = {e, adj[s].next};
    adj[s].next = buf + bCnt++;
}
 
void reGroup(int k){
    group[k] = gn;
    for(Node*p = adj+k;p->next;){
        if(used[p->next->node]){
            p->next = p->next->next;
        }
        else{
            reGroup(p->next->node);
            p = p->next;
        }
    }
}
 
void split(int a, int b){
    if(a==0) return;
    par[b] = 0;
    used[b] = 1;
    a = gtop[group[a]];
 
    int flag = 0;
    xf = xe = yf = ye = 0;
    xQue[xe++] = {adj+a};
    yQue[ye++] = {adj+b};
    while(1){
        while(xf<xe && !xQue[xf].hasNext())
            ++xf;
        if(xf >= xe)
            break;
        xQue[xe++] = {adj + xQue[xf].now->node};
 
        while(yf<ye && !yQue[yf].hasNext())
            ++yf;
        if(yf >= ye){
            flag = 1;
            break;
        }
        yQue[ye++] = {adj + yQue[yf].now->node};
    }
    gn++;
    if(flag){
        gtop[gn] = b;
        reGroup(b);
    }
    else{
        gtop[group[a]] = b;
        gtop[gn] = a;
        reGroup(a);
    }
}
 
int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &Q);
    int i, b, c, d;
    for(i=2;i<=N;++i){
        scanf("%d", &b);
        par[i] = b;
        push_adj(b, i);
    }
 
    for(i=0;i<Q;++i){
        scanf("%d %d %d", &b, &c, &d);
        int flag = group[b]==group[c];
        puts(flag? "YES":"NO");
        if(d){
            if(flag) split(par[b], b);
            else split(par[c], c);
        }
    }
    return 0;
}

Compilation message (stderr)

tree.cpp: In function 'int main()':
tree.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~
tree.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b);
         ~~~~~^~~~~~~~~~
tree.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &b, &c, &d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 14 / 14
• Subtask 4: 19 / 19
• Subtask 5: 45 / 45