fork download
copy 
  1. #include <stdio.h>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. inline int fast_input(void)
  6. {
  7. 	char t;
  8. 	int x=0;
  9. 	int neg=0;
  10. 	t=getchar();
  11. 	while((t<48 || t>57) && t!='-')
  12. 		t=getchar();
  13. 	if(t=='-')
  14. 		{neg=1; t=getchar();}
  15.     while(t>=48 && t<=57)
  16.     {
  17.         x=(x<<3)+(x<<1)+t-48;
  18.         t=getchar();
  19.     }
  20. 	if(neg)
  21. 		x=-x;
  22. 	return x;
  23. }
  24.  
  25. inline void fast_output(int x)
  26. {
  27. 	char a[20];
  28. 	int i=0,j;
  29. 	a[0]='0';
  30. 	if (x<0) {putchar('-'); x=-x;}
  31. 	if (x==0) putchar('0');
  32. 	while(x)
  33. 	{
  34. 		a[i++]=x%10+48;
  35. 		x/=10;
  36. 	}
  37. 	for(j=i-1;j>=0;j--)
  38. 	{
  39. 		putchar(a[j]);
  40. 	}
  41. 	putchar('\n');
  42. }
  43.  
  44. int f[100001],r[100001],root[100001],visited[100001],child[100001],isroot[100001];
  45.  
  46. void dfs(int i, int j)
  47. {
  48. 	visited[i]=j;
  49. 	if (!visited[f[i]])
  50. 	{
  51. 		dfs(f[i],j);
  52. 		if (root[f[i]]!=0&&root[f[i]]!=f[i]) {root[i]=root[f[i]]; if (root[i]!=i) r[root[i]]+=r[i];}
  53. 		else child[i]=f[i];
  54. 	}
  55. 	else
  56. 	{
  57. 		if (visited[f[i]]!=j)
  58. 		{
  59. 			if (root[f[i]]==0) child[i]=f[i];
  60. 			else child[i]=root[f[i]];
  61. 		}
  62. 		else
  63. 		{
  64. 			root[i]=f[i];
  65. 			r[root[i]]+=r[i];
  66. 			isroot[j-1]=f[i];
  67. 		}
  68. 	}
  69. }
  70.  
  71. int bfs(int v, vector <int> G[100001])
  72. {
  73. 	int ans=0,i,len=G[v].size(),temp;
  74. 	for(i=0;i<len;i++)
  75. 	{
  76. 		temp=bfs(G[v][i],G);
  77. 		if (temp>0) ans+=temp;
  78. 	}
  79. 	if (ans+r[v]>0) return ans+r[v];
  80. 	else return 0;
  81. }
  82.  
  83. int main()
  84. {
  85. int t,i,j,n,ans;
  86. t=fast_input();
  87. while(t--)
  88. {
  89. 	ans=0;
  90. 	n=fast_input();
  91. 	for(i=1;i<=n;i++) f[i]=fast_input();
  92. 	for(i=1;i<=n;i++) r[i]=fast_input();
  93. 	for(i=1;i<=n;i++) 
  94. 	{
  95. 		visited[i]=0;
  96. 		isroot[i]=0;
  97. 		child[i]=0;
  98. 		root[i]=0;
  99. 	}
  100. 	vector <int> G[100001];
  101. 	j=1;
  102. 	for(i=1;i<=n;i++) if (!visited[i]) {dfs(i,j); j++;}
  103. 	for(i=1;i<=n;i++) if (child[i]) G[child[i]].push_back(i);
  104. 	for(i=0;i<j;i++) ans+=bfs(isroot[i],G);
  105. 	fast_output(ans);
  106. }
  107. return 0;
  108. }
  109.  
Success #stdin #stdout 0s 6672KB
comments (?)
stdin
copy 
3
6
2 3 1 1 2 3
-1 -1 -1 2 2 2
5
5 1 4 5 4 
-964684432 74513386 -390331583 309950241 202556218 
6
5 3 1 3 3 2
1 -10 3 -2 4 -5
stdout
copy 
3
512506459
8
https://ideone.com/owYttZ
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!