Submission #57845

#TimeUsernameProblemLanguageResultExecution timeMemory
57845red1108트리 (KOI16_tree)C++17
55 / 100
2064 ms25940 KiB
#include <stdio.h> #include <vector> #include <set> using namespace std; int n,q; vector<int> tree[200010]; int seg[800010],par[200010],cnt=0,si=1,color[200010],ccnt=1,bumo[200010],cut[200010]; pair<int,int> range[200010]; int checkcnt=0; void dfs(int x) { range[x].first=++cnt; for(auto i:tree[x]) dfs(i); range[x].second=cnt; } void rename(int x,int newc) { checkcnt++; color[x]=newc; for(auto i:tree[x]) if(!cut[i]) rename(i,newc); } void gang(int x, int k) { x=x+si-1; int delta=k-seg[x]; while(x) { seg[x]+=delta; x/=2; } } int getsize(int x, int l, int r, int s, int e) { if(l>r||e<l||r<s)return 0; if(s<=l&&r<=e)return seg[x]; return getsize(x*2,l,(l+r)/2,s,e)+getsize(x*2+1,(l+r)/2+1,r,s,e); } int main() { int i,a,b,c,flag,tmp,sip,sia; scanf("%d %d", &n,&q); while(si<n)si*=2; for(i=2; i<=n; i++) { scanf("%d", &a); bumo[i]=a; tree[a].emplace_back(i); } for(i=1;i<=n;i++) color[i]=1; par[1]=1; dfs(1); for(i=1;i<=n;i++) gang(i,1); for(i=1;i<=q;i++,flag=0) { scanf("%d %d %d", &a, &b, &c); if(color[a]==color[b]) { printf("YES\n"); flag=1; } else printf("NO\n"); if(c==0) continue; if(!flag) a=b; if(cut[a]) continue; cut[a]=1; sia=getsize(1,1,si,range[a].first+1,range[a].second)+1; gang(range[a].first,(-1)*sia+1); sip=getsize(1,1,si,range[par[color[a]]].first+1,range[par[color[a]]].second)+1; if(sip<sia) { par[ccnt+1]=par[color[a]]; tmp=color[a]; rename(par[color[a]],++ccnt); par[tmp]=a; } else { rename(a,++ccnt); par[ccnt]=a; } } }

Compilation message (stderr)

tree.cpp: In function 'int main()':
tree.cpp:41: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:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~
tree.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...