fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1000005;
  5.  
  6. int n, p1[N], p2[N];
  7. int a[N], b[N];
  8. vector<int> g1[N], g2[N];
  9. int in1[N], out1[N], in2[N], out2[N], timer1 = 0, timer2 = 0;
  10. int fen1[N], fen2[N];
  11.  
  12. void upd(int fen[], int i, int v){
  13.     for(; i<=n; i+=i&-i) fen[i]+=v;
  14. }
  15. int get(int fen[], int i){
  16.     int s=0;
  17.     for(; i>0; i-=i&-i) s+=fen[i];
  18.     return s;
  19. }
  20. void range_upd(int fen[], int l, int r, int v){
  21.     upd(fen,l,v);
  22.     upd(fen,r+1,-v);
  23. }
  24.  
  25. void dfs1(int u){
  26.     in1[u]=++timer1;
  27.     for(int v: g1[u]) dfs1(v);
  28.     out1[u]=timer1;
  29. }
  30. void dfs2(int u){
  31.     in2[u]=++timer2;
  32.     for(int v: g2[u]) dfs2(v);
  33.     out2[u]=timer2;
  34. }
  35.  
  36. int keep[N];
  37.  
  38. void solve_dfs(int u){
  39.     for(int v: g1[u]) solve_dfs(v);
  40.  
  41.     int sz1 = get(fen1, in1[u]);
  42.     int sz2 = get(fen2, in2[u]);
  43.  
  44.     if(sz1 < a[u] || sz2 < b[u]){
  45.         keep[u] = 0;
  46.         range_upd(fen1, in1[u], out1[u], -1);
  47.         range_upd(fen2, in2[u], out2[u], -1);
  48.     }
  49. }
  50.  
  51. int main(){
  52.     ios::sync_with_stdio(false);
  53.     cin.tie(0);
  54.  
  55.     cin>>n;
  56.     for(int i=1;i<=n;i++){
  57.         cin>>p1[i];
  58.         if(p1[i]) g1[p1[i]].push_back(i);
  59.     }
  60.     for(int i=1;i<=n;i++){
  61.         cin>>p2[i];
  62.         if(p2[i]) g2[p2[i]].push_back(i);
  63.     }
  64.     for(int i=1;i<=n;i++) cin>>a[i];
  65.     for(int i=1;i<=n;i++) cin>>b[i];
  66.  
  67.     for(int i=1;i<=n;i++) if(!p1[i]) dfs1(i);
  68.     for(int i=1;i<=n;i++) if(!p2[i]) dfs2(i);
  69.  
  70.     for(int i=1;i<=n;i++){
  71.         keep[i] = 1;
  72.         range_upd(fen1, in1[i], in1[i], 1);
  73.         range_upd(fen2, in2[i], in2[i], 1);
  74.     }
  75.  
  76.     for(int i=1;i<=n;i++) if(!p1[i]) solve_dfs(i);
  77.  
  78.     int ans = 0;
  79.     for(int i=1;i<=n;i++) if(keep[i]) ans++;
  80.  
  81.     cout << ans;
  82. }
  83.  
Success #stdin #stdout 0.02s 69208KB
comments (?)
stdin
copy 
5
5 5 5 5 0
0 1 1 2 2
1 1 1 0 2
0 2 0 0 0
stdout
copy 
3
https://ideone.com/N242oS
language:
C++14 (clang 8.0)
created:
23 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!