Submission #26712

#	Time	Username	Problem	Language	Result	Execution time	Memory
26712		dongwon0427	트리 (KOI16_tree)	C++98	0 / 100	0 ms	36532 KiB

tree

#include <bits/stdc++.h>
using namespace std;
int n,q;
vector<int> graph[200005];
int H[200005];
int vt[200005];
int E[200005];
vector<int> G[200005];
int depth[200005];
int dfs(int idx,int cnt) {
    H[idx]=cnt;
    vt[idx]=1;
    //printf("%d : %d\n",idx,cnt);
    for(int i=0;i<graph[idx].size();i++) {
        int nxt=graph[idx][i];
        if(vt[nxt]==0) {
            cnt=dfs(nxt,++cnt)+1;
        }
    }
    E[H[idx]]=cnt;
    return cnt-1;
}
int ANC[200005][22];
int vtANC[200005];
void anc(int idx){
    if(vtANC[idx]==1) return;
    vtANC[idx]=1;
    for(int i=0;i<G[idx].size();i++) {
        int nxt=G[idx][i];
        ANC[nxt][0]=idx;
        for(int i=1;1;i++) {
            if(ANC[nxt][i-1]==-1) break;
            ANC[nxt][i]=ANC[ANC[nxt][i-1]][i-1];
        }
        if(vtANC[nxt]==0) depth[nxt]=depth[idx]+1;
        anc(nxt);
    }
}
int segtree[800008];
int sum(int idx,int s,int e,int k) {
    if(s==e) {
        return segtree[idx];
    }
    segtree[idx*2]=max(segtree[idx*2],segtree[idx]);
    segtree[idx*2+1]=max(segtree[idx*2+1],segtree[idx]);
    segtree[idx]=0;
    if(s<=k && k<=(s+e)/2) {
        return sum(idx*2,s,(s+e)/2,k);
    } else {
        return sum(idx*2+1,(s+e)/2+1,e,k);
    }
}
int getA(int idx,int num) {
    if(num==0) return idx;
    if(num>depth[idx]) return -1;
    int i=0;
    while(num!=0) {
        if(num%2) idx=ANC[idx][i];
        num=num>>1;
        i++;
    }
}
void updt(int idx,int s,int e,int l,int r,int key) {
    //printf("ㄴㄱㅁ\n");
    if(l<=s && e<=r) {
        segtree[idx]=max(segtree[idx],key);
        return;
    }
    if(e<l || r<s) {
        return;
    }
    updt(idx*2,s,(s+e)/2,l,r,key);
    updt(idx*2+1,(s+e)/2+1,e,l,r,key);
}
int cutvt[200005];
int main() {
    //freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&q);
    for(int i=2;i<=n;i++) {
        int tmp;
        scanf("%d",&tmp);
        graph[tmp].push_back(i);
    }
    dfs(1,1);
    //for(int i=1;i<=n;i++) printf("%d ",E[i]);
    //printf("\n");
    for(int i=1;i<=n;i++) {
        for(int j=0;j<graph[i].size();j++) {
            G[H[i]].push_back(H[graph[i][j]]);
        }
    }
    for(int i=1;i<=n;i++) fill(ANC[i],ANC[i]+22,-1);
    anc(1);
    /*for(int i=1;i<=n;i++) {
        printf("%d : ",i);
        for(int j=0;j<G[i].size();j++) {
            printf("%d ",G[i][j]);
        }
        printf("\n");
    }*/
    cutvt[1]=1;
    for(int i=1;i<=q;i++) {
        int t1,t2,t3;
        scanf("%d%d%d",&t1,&t2,&t3);
        t2=H[t2];t1=H[t1];
        int a=sum(1,1,n,t1); int b=sum(1,1,n,t2);
        int aA=getA(t1,depth[t1]-a);int bA=getA(t2,depth[t2]-b);
        //printf("%d %d\n",depth[t1]-a,depth[t2]-b);
        //printf("%d %d\n",aA,bA);
        if(aA==bA) printf("YES\n");
        else printf("NO\n");
        if(t3==1) {
            if(aA==bA) {
                //앞에 제거
                if(cutvt[t1]!=1) updt(1,1,n,t1,E[t1],depth[t1]);
                cutvt[t1]=1;
            } else {
                if(cutvt[t2]!=1) updt(1,1,n,t2,E[t2],depth[t2]);
                cutvt[t2]=1;
            }
        }
    }
    //printf("%d",getA(4,0));
    //for(int i=1;i<=n;i++) printf("%d : %d\n",i,depth[i]);
    return 0;
}

Compilation message (stderr)

tree.cpp: In function 'int dfs(int, int)':
tree.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<graph[idx].size();i++) {
                  ^
tree.cpp:17:33: warning: operation on 'cnt' may be undefined [-Wsequence-point]
             cnt=dfs(nxt,++cnt)+1;
                                 ^
tree.cpp: In function 'void anc(int)':
tree.cpp:28:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<G[idx].size();i++) {
                  ^
tree.cpp: In function 'int main()':
tree.cpp:88:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<graph[i].size();j++) {
                      ^
tree.cpp: In function 'int getA(int, int)':
tree.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
tree.cpp: In function 'int main()':
tree.cpp:78:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&q);
                        ^
tree.cpp:81:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&tmp);
                         ^
tree.cpp:104:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&t1,&t2,&t3);
                                    ^

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