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
AC × 5
AC × 94
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