fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define pii pair<int,int>
  13. #define pil pair<int,ll>
  14. #define pli pair<ll,int>
  15. #define MOD 1000000007
  16. #define el "\n"
  17.  
  18. const int MAX=1e5+5;
  19. int n,bit[2*MAX],tin[MAX],tout[MAX],root1,root2,timer;
  20. vector<int> adj1[MAX], adj2[MAX];
  21. ll res=0;
  22.  
  23. void dfs1(int u)
  24. {
  25.     tin[u]=++timer;
  26.     for(int v:adj1[u]) dfs1(v);
  27.     tout[u]=timer;
  28. }
  29.  
  30. void update(int pos, int val)
  31. {
  32.     for(;pos<=n;pos+=(pos&(-pos))) bit[pos]+=val;
  33. }
  34.  
  35. int query(int pos)
  36. {
  37.     int ans=0;
  38.     for(;pos>=1;pos-=(pos&(-pos))) ans+=bit[pos];
  39.     return ans;
  40. }
  41.  
  42. void dfs2(int u)
  43. {
  44.     int tmp=query(tin[u]);
  45.     res+=tmp;
  46.     update(tin[u],1);
  47.     update(tout[u]+1,-1);
  48.     for(int v:adj2[u]) dfs2(v);
  49.     update(tin[u],-1);
  50.     update(tout[u]+1,1);
  51. }
  52.  
  53. int main()
  54. {
  55.     fastio
  56.  
  57.     cin>>n;
  58.     foru(i,1,n)
  59.     {
  60.         int x; cin>>x;
  61.         if(x!=0) adj1[x].pb(i);
  62.         else root1=i;
  63.     }
  64.     dfs1(root1);
  65.     foru(i,1,n)
  66.     {
  67.         int x; cin>>x;
  68.         if(x!=0) adj2[x].pb(i);
  69.         else root2=i;
  70.     }
  71.     dfs2(root2);
  72.     cout<<res;
  73.  
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0.01s 8136KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xpPaAx
language:
C++14 (gcc 8.3)
created:
2 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!