Submission #2968442
Source Code Expand
#include <iostream> #include <algorithm> #include <vector> #include <cstdio> using namespace std; int n,k,q,sz[100005],hv[100005],vs[100005],hd[100005],dp[100005],cn[100005],id[1000005],seg[1<<19],pa[100005],c[100005]; vector<int>g[100005]; void dfs(int v,int p){ sz[v]=1; hv[v]=-1; for(int i=0;i<g[v].size();i++){ if(g[v][i]!=p){ dfs(g[v][i],v); sz[v]+=sz[g[v][i]]; if(hv[v]==-1||sz[hv[v]]<sz[g[v][i]])hv[v]=g[v][i]; } } } void dfs1(int v,int d,int p,int h){ hd[k]=h; cn[k]=cn[h]; id[v]=k; vs[k]=v; dp[k++]=d; if(hv[v]!=-1)dfs1(hv[v],d+1,v,h); for(int i=0;i<g[v].size();i++){ if(g[v][i]!=p&&g[v][i]!=hv[v]){ cn[k]=id[v]; dfs1(g[v][i],d+1,v,k); } } } void add(int a,int b){ a+=(1<<18)-1; seg[a]+=b; while(a>0){ a=(a-1)/2; seg[a]+=b; } } int que(int a,int b,int l,int r,int o){ if(r<a||b<l)return 0; if(a<=l&&r<=b)return seg[o]; return que(a,b,l,(l+r-1)/2,o*2+1)+que(a,b,(l+r+1)/2,r,o*2+2); } int lca(int u,int v){ int res=0; u=id[u];v=id[v]; while(hd[u]!=hd[v]){ if(dp[hd[u]]>dp[hd[v]]){ res+=que(hd[u],u,0,(1<<18)-1,0); u=cn[u]; }else{ res+=que(hd[v],v,0,(1<<18)-1,0); v=cn[v]; } } return res+que(min(u,v)+1,max(u,v),0,(1<<18)-1,0); } int main(void){ cin>>n; for(int i=1;i<n;i++){ cin>>pa[i]; g[--pa[i]].push_back(i); } dfs(0,-1); dfs1(0,0,-1,0); for(int i=0;i<n;i++){ cin>>c[i]; } for(int i=1;i<n;i++){ if(c[i]==c[pa[i]]){ pa[i]=1; add(id[i],1); }else pa[i]=0; } cin>>q; for(int i=0;i<q;i++){ int t; cin>>t; if(t==1){ int v; cin>>v; v--; if(v==0)continue; if(pa[v]==1){ add(id[v],-1); pa[v]=0; }else{ add(id[v],1); pa[v]=1; } }else{ int u,v; cin>>u>>v; u--; v--; if(lca(u,v)==0)cout<<"YES\n"; else cout<<"NO\n"; } } }
Submission Info
Submission Time | |
---|---|
Task | H - 白黒ツリー |
User | nxteru |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2370 Byte |
Status | AC |
Exec Time | 431 ms |
Memory | 20992 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1000 / 1000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04 |
All | 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 01_graph_random_color_random_query_random_00, 01_graph_random_color_random_query_random_01, 01_graph_random_color_random_query_random_02, 01_graph_random_color_random_query_random_03, 01_graph_random_color_random_query_random_04, 01_graph_random_color_random_query_random_05, 01_graph_random_color_random_query_random_06, 01_graph_random_color_random_query_random_07, 01_graph_random_color_random_query_random_08, 01_graph_random_color_random_query_random_09, 02_graph_random_color_same_query_random_00, 02_graph_random_color_same_query_random_01, 02_graph_random_color_same_query_random_02, 02_graph_random_color_same_query_random_03, 02_graph_random_color_same_query_random_04, 02_graph_random_color_same_query_random_05, 02_graph_random_color_same_query_random_06, 02_graph_random_color_same_query_random_07, 02_graph_random_color_same_query_random_08, 02_graph_random_color_same_query_random_09, 03_graph_random_color_alternate_query_random_00, 03_graph_random_color_alternate_query_random_01, 03_graph_random_color_alternate_query_random_02, 03_graph_random_color_alternate_query_random_03, 03_graph_random_color_alternate_query_random_04, 03_graph_random_color_alternate_query_random_05, 03_graph_random_color_alternate_query_random_06, 03_graph_random_color_alternate_query_random_07, 03_graph_random_color_alternate_query_random_08, 03_graph_random_color_alternate_query_random_09, 10_graph_path_color_alternate_query_all2_00, 10_graph_path_color_random_query_random_00, 10_graph_path_color_random_query_random_01, 10_graph_path_color_random_query_random_02, 10_graph_path_color_random_query_random_03, 10_graph_path_color_random_query_random_04, 10_graph_path_color_random_query_random_05, 10_graph_path_color_same_query_all2_00, 10_graph_path_color_sametoAlternate_query_11...12_00, 20_graph_star_color_alternate_query_all2_00, 20_graph_star_color_random_query_1Center2random_00, 20_graph_star_color_random_query_1Center2random_01, 20_graph_star_color_random_query_1Center2random_02, 20_graph_star_color_random_query_1Center2random_03, 20_graph_star_color_random_query_1Center2random_04, 20_graph_star_color_random_query_1Center2random_05, 20_graph_star_color_random_query_1Center2random_06, 20_graph_star_color_random_query_1Center2random_07, 20_graph_star_color_random_query_1Center2random_08, 20_graph_star_color_random_query_1Center2random_09, 20_graph_star_color_random_query_1Center2random_10, 20_graph_star_color_random_query_random_00, 20_graph_star_color_random_query_random_01, 20_graph_star_color_random_query_random_02, 20_graph_star_color_random_query_random_03, 20_graph_star_color_random_query_random_04, 20_graph_star_color_random_query_random_05, 20_graph_star_color_same_query_all2_00, 20_graph_star_color_sametoAlternate_query_11...12_00, 30_graph_hitode_color_random_query_random_00, 30_graph_hitode_color_random_query_random_01, 30_graph_hitode_color_random_query_random_02, 30_graph_hitode_color_random_query_random_03, 30_graph_hitode_color_random_query_random_04, 30_graph_hitode_color_random_query_random_05, 40_graph_caterpillar_color_random_query_random_00, 40_graph_caterpillar_color_random_query_random_01, 40_graph_caterpillar_color_random_query_random_02, 40_graph_caterpillar_color_random_query_random_03, 40_graph_caterpillar_color_random_query_random_04, 40_graph_caterpillar_color_random_query_random_05, 50_graph_binaryTree_color_random_query_random_00, 50_graph_binaryTree_color_random_query_random_01, 50_graph_binaryTree_color_random_query_random_02, 50_graph_binaryTree_color_random_query_random_03, 50_graph_binaryTree_color_random_query_random_04, 50_graph_binaryTree_color_random_query_random_05, 60_graph_ternaryTree_color_random_query_random_00, 60_graph_ternaryTree_color_random_query_random_01, 60_graph_ternaryTree_color_random_query_random_02, 60_graph_ternaryTree_color_random_query_random_03, 60_graph_ternaryTree_color_random_query_random_04, 60_graph_ternaryTree_color_random_query_random_05, 70_graph_triangle_color_random_query_random_00, 70_graph_triangle_color_random_query_random_01, 70_graph_triangle_color_random_query_random_02, 70_graph_triangle_color_random_query_random_03, 70_graph_triangle_color_random_query_random_04, 70_graph_triangle_color_random_query_random_05 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00 | AC | 4 ms | 8448 KB |
00_sample_01 | AC | 3 ms | 8448 KB |
00_sample_02 | AC | 3 ms | 8448 KB |
00_sample_03 | AC | 3 ms | 8448 KB |
00_sample_04 | AC | 3 ms | 8448 KB |
01_graph_random_color_random_query_random_00 | AC | 75 ms | 9344 KB |
01_graph_random_color_random_query_random_01 | AC | 44 ms | 8960 KB |
01_graph_random_color_random_query_random_02 | AC | 30 ms | 8576 KB |
01_graph_random_color_random_query_random_03 | AC | 25 ms | 9088 KB |
01_graph_random_color_random_query_random_04 | AC | 51 ms | 9088 KB |
01_graph_random_color_random_query_random_05 | AC | 65 ms | 8832 KB |
01_graph_random_color_random_query_random_06 | AC | 65 ms | 8960 KB |
01_graph_random_color_random_query_random_07 | AC | 91 ms | 10112 KB |
01_graph_random_color_random_query_random_08 | AC | 83 ms | 9472 KB |
01_graph_random_color_random_query_random_09 | AC | 74 ms | 9728 KB |
02_graph_random_color_same_query_random_00 | AC | 63 ms | 8960 KB |
02_graph_random_color_same_query_random_01 | AC | 124 ms | 10112 KB |
02_graph_random_color_same_query_random_02 | AC | 36 ms | 9600 KB |
02_graph_random_color_same_query_random_03 | AC | 208 ms | 9472 KB |
02_graph_random_color_same_query_random_04 | AC | 108 ms | 9728 KB |
02_graph_random_color_same_query_random_05 | AC | 84 ms | 10496 KB |
02_graph_random_color_same_query_random_06 | AC | 32 ms | 8704 KB |
02_graph_random_color_same_query_random_07 | AC | 114 ms | 10112 KB |
02_graph_random_color_same_query_random_08 | AC | 36 ms | 9216 KB |
02_graph_random_color_same_query_random_09 | AC | 33 ms | 8832 KB |
03_graph_random_color_alternate_query_random_00 | AC | 20 ms | 8832 KB |
03_graph_random_color_alternate_query_random_01 | AC | 65 ms | 10108 KB |
03_graph_random_color_alternate_query_random_02 | AC | 21 ms | 9344 KB |
03_graph_random_color_alternate_query_random_03 | AC | 61 ms | 9088 KB |
03_graph_random_color_alternate_query_random_04 | AC | 41 ms | 9216 KB |
03_graph_random_color_alternate_query_random_05 | AC | 58 ms | 9856 KB |
03_graph_random_color_alternate_query_random_06 | AC | 81 ms | 16640 KB |
03_graph_random_color_alternate_query_random_07 | AC | 71 ms | 9344 KB |
03_graph_random_color_alternate_query_random_08 | AC | 107 ms | 12160 KB |
03_graph_random_color_alternate_query_random_09 | AC | 93 ms | 10496 KB |
10_graph_path_color_alternate_query_all2_00 | AC | 345 ms | 20992 KB |
10_graph_path_color_random_query_random_00 | AC | 308 ms | 20864 KB |
10_graph_path_color_random_query_random_01 | AC | 137 ms | 20608 KB |
10_graph_path_color_random_query_random_02 | AC | 126 ms | 20608 KB |
10_graph_path_color_random_query_random_03 | AC | 128 ms | 20608 KB |
10_graph_path_color_random_query_random_04 | AC | 126 ms | 20608 KB |
10_graph_path_color_random_query_random_05 | AC | 127 ms | 20608 KB |
10_graph_path_color_same_query_all2_00 | AC | 345 ms | 20864 KB |
10_graph_path_color_sametoAlternate_query_11...12_00 | AC | 126 ms | 20608 KB |
20_graph_star_color_alternate_query_all2_00 | AC | 346 ms | 10488 KB |
20_graph_star_color_random_query_1Center2random_00 | AC | 348 ms | 10488 KB |
20_graph_star_color_random_query_1Center2random_01 | AC | 325 ms | 10488 KB |
20_graph_star_color_random_query_1Center2random_02 | AC | 310 ms | 10360 KB |
20_graph_star_color_random_query_1Center2random_03 | AC | 272 ms | 10360 KB |
20_graph_star_color_random_query_1Center2random_04 | AC | 258 ms | 10360 KB |
20_graph_star_color_random_query_1Center2random_05 | AC | 243 ms | 10360 KB |
20_graph_star_color_random_query_1Center2random_06 | AC | 213 ms | 10232 KB |
20_graph_star_color_random_query_1Center2random_07 | AC | 191 ms | 10232 KB |
20_graph_star_color_random_query_1Center2random_08 | AC | 164 ms | 10232 KB |
20_graph_star_color_random_query_1Center2random_09 | AC | 140 ms | 10104 KB |
20_graph_star_color_random_query_1Center2random_10 | AC | 117 ms | 10104 KB |
20_graph_star_color_random_query_random_00 | AC | 257 ms | 10360 KB |
20_graph_star_color_random_query_random_01 | AC | 136 ms | 10104 KB |
20_graph_star_color_random_query_random_02 | AC | 118 ms | 10104 KB |
20_graph_star_color_random_query_random_03 | AC | 118 ms | 10104 KB |
20_graph_star_color_random_query_random_04 | AC | 116 ms | 10104 KB |
20_graph_star_color_random_query_random_05 | AC | 118 ms | 10104 KB |
20_graph_star_color_same_query_all2_00 | AC | 352 ms | 10488 KB |
20_graph_star_color_sametoAlternate_query_11...12_00 | AC | 116 ms | 10104 KB |
30_graph_hitode_color_random_query_random_00 | AC | 364 ms | 15616 KB |
30_graph_hitode_color_random_query_random_01 | AC | 146 ms | 15360 KB |
30_graph_hitode_color_random_query_random_02 | AC | 140 ms | 15360 KB |
30_graph_hitode_color_random_query_random_03 | AC | 136 ms | 15360 KB |
30_graph_hitode_color_random_query_random_04 | AC | 137 ms | 15360 KB |
30_graph_hitode_color_random_query_random_05 | AC | 135 ms | 15360 KB |
40_graph_caterpillar_color_random_query_random_00 | AC | 283 ms | 10488 KB |
40_graph_caterpillar_color_random_query_random_01 | AC | 128 ms | 10240 KB |
40_graph_caterpillar_color_random_query_random_02 | AC | 115 ms | 10232 KB |
40_graph_caterpillar_color_random_query_random_03 | AC | 113 ms | 10240 KB |
40_graph_caterpillar_color_random_query_random_04 | AC | 113 ms | 10240 KB |
40_graph_caterpillar_color_random_query_random_05 | AC | 113 ms | 10208 KB |
50_graph_binaryTree_color_random_query_random_00 | AC | 431 ms | 11392 KB |
50_graph_binaryTree_color_random_query_random_01 | AC | 175 ms | 11264 KB |
50_graph_binaryTree_color_random_query_random_02 | AC | 129 ms | 11136 KB |
50_graph_binaryTree_color_random_query_random_03 | AC | 129 ms | 11136 KB |
50_graph_binaryTree_color_random_query_random_04 | AC | 128 ms | 11136 KB |
50_graph_binaryTree_color_random_query_random_05 | AC | 129 ms | 11136 KB |
60_graph_ternaryTree_color_random_query_random_00 | AC | 174 ms | 10752 KB |
60_graph_ternaryTree_color_random_query_random_01 | AC | 145 ms | 10624 KB |
60_graph_ternaryTree_color_random_query_random_02 | AC | 131 ms | 10624 KB |
60_graph_ternaryTree_color_random_query_random_03 | AC | 127 ms | 10624 KB |
60_graph_ternaryTree_color_random_query_random_04 | AC | 128 ms | 10624 KB |
60_graph_ternaryTree_color_random_query_random_05 | AC | 127 ms | 10624 KB |
70_graph_triangle_color_random_query_random_00 | AC | 339 ms | 13056 KB |
70_graph_triangle_color_random_query_random_01 | AC | 136 ms | 12800 KB |
70_graph_triangle_color_random_query_random_02 | AC | 135 ms | 12800 KB |
70_graph_triangle_color_random_query_random_03 | AC | 133 ms | 12800 KB |
70_graph_triangle_color_random_query_random_04 | AC | 134 ms | 12800 KB |
70_graph_triangle_color_random_query_random_05 | AC | 134 ms | 12800 KB |