fork download 
  1. //teja349
  2. #include <bits/stdc++.h>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <string>
  7. #include <cstdio>
  8. #include <cstdlib>
  9. #include <climits>
  10. #include <utility>
  11. #include <algorithm>
  12. #include <cmath>
  13. #include <queue>
  14. #include <stack>
  15. #include <iomanip> 
  16. //setbase - cout << setbase (16); cout << 100 << endl; Prints 64
  17. //setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
  18. //setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
  19.  
  20.  
  21. using namespace std;
  22. #define f(i,a,b) for(i=a;i<b;i++)
  23. #define rep(i,n) f(i,0,n)
  24. #define fd(i,a,b) for(i=a;i>=b;i--)
  25. #define pb push_back
  26. #define mp make_pair
  27. #define vi vector< int >
  28. #define vl vector< ll >
  29. #define ss second
  30. #define ff first
  31. #define ll long long
  32. #define pii pair< int,int >
  33. #define pll pair< ll,ll >
  34. #define sz(a) a.size()
  35. #define inf (1000*1000*1000+5)
  36. #define all(a) a.begin(),a.end()
  37. #define tri pair<ll,pll>
  38. #define vii vector<pii>
  39. #define vll vector<pll>
  40. #define viii vector<tri>
  41. #define mod (1000*1000*1000+7)
  42. #define pqueue priority_queue< int >
  43. #define pdqueue priority_queue< int,vi ,greater< int > >
  44. ll prim =(727999983);
  45. //std::ios::sync_with_stdio(false);   
  46. vector<vi> adj1(123456),adj2(123456);
  47. ll cntable[123456],subtree[123456],ans2[123456];
  48.  
  49. int dfs2(int cur,int par){
  50. 	vl vec1;
  51. 	ll i;
  52. 	subtree[cur]=1;
  53. 	rep(i,adj2[cur].size()){
  54. 		dfs2(adj2[cur][i],cur);
  55. 		subtree[cur]+=subtree[adj2[cur][i]];
  56. 	}
  57. 	if(adj2[cur].empty()){
  58. 		ans2[cur]=1997;
  59. 		return 0;
  60. 	}
  61. 	rep(i,adj2[cur].size()){
  62. 		vec1.pb(ans2[adj2[cur][i]]);
  63. 	}
  64. 	sort(vec1.begin(),vec1.end());
  65. 	ll haha=0;
  66. 	ll val=173;
  67. 	rep(i,vec1.size()){
  68. 		haha+=vec1[i]*val;
  69.  
  70. 		val*=prim;
  71. 		haha*=vec1[i];
  72. 	}
  73. 	ans2[cur]=haha;
  74. 	return 0;
  75. }
  76. int dfs1(int cur,int par){
  77. 	vl vec1;
  78. 	ll i;
  79. 	set< tri > vec2;
  80. 	set< tri >::iterator it;
  81. 	subtree[cur]=1;
  82. 	rep(i,adj1[cur].size()){
  83. 		dfs1(adj1[cur][i],cur);
  84. 		subtree[cur]+=subtree[adj1[cur][i]];
  85. 	}
  86. 	if(adj1[cur].empty()){
  87. 		ans2[cur]=1997;
  88. 		cntable[cur]=1;
  89. 		return 0;
  90. 	}
  91. 	rep(i,adj1[cur].size()){
  92. 		vec1.pb(ans2[adj1[cur][i]]);
  93. 		vec2.insert(mp(cntable[adj1[cur][i]],mp(subtree[adj1[cur][i]],ans2[adj1[cur][i]])));
  94. 	}
  95.  
  96. 	sort(vec1.begin(),vec1.end());
  97. 	ll haha=0;
  98. 	ll val=173;
  99. 	rep(i,vec1.size()){
  100. 		haha+=vec1[i]*val;
  101. 		val*=prim;
  102. 		haha*=vec1[i];
  103.  
  104. 	}
  105. 	ans2[cur]=haha;
  106. 	cntable[cur]=0;
  107. 	for(it=vec2.begin();it!=vec2.end();it++){
  108. 		cntable[cur]+=it->ff;
  109. 	}
  110. 	return 0;
  111. }
  112.  
  113. int main(){
  114.     std::ios::sync_with_stdio(false);
  115.     int t;
  116.     cin>>t;
  117.     while(t--){
  118.     	int n1,n2;
  119.     	cin>>n1>>n2;
  120.     	int i,u;
  121.     	rep(i,n1){
  122.     		adj1[i].clear();
  123.     	}
  124.     	rep(i,n2){
  125.     		adj2[i].clear();
  126.     	}
  127.     	f(i,1,n1){
  128.     		cin>>u;
  129.     		u--;
  130.  
  131.     		adj1[u].pb(i);
  132.     		//adj1[i].pb(u);
  133.  
  134.     	}
  135.     	f(i,1,n2){
  136.     		cin>>u;
  137.     		u--;
  138.  
  139.     		adj2[u].pb(i);
  140.     		//adj2[i].pb(u);
  141.  
  142.     	}
  143.     	dfs2(0,-1);
  144.     	set<pll> seti;
  145.     	rep(i,n2){
  146.     		seti.insert(mp(subtree[i],ans2[i]));
  147.     	}
  148.     	ll distinct=seti.size();
  149.     	dfs1(0,-1);
  150.     	distinct*=cntable[0];
  151.     	cout<<distinct<<"\n";
  152.     }
  153.     return 0;  
  154.  
  155. }
Runtime error #stdin #stdout #stderr 0s 93376KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/oB036C
language:
C++ (gcc 8.3)
created:
6 years 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!