fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=200000+10;
  27.  
  28. int n;
  29. int x[MAX],y[MAX];
  30. int p1[MAX],p2[MAX],num[MAX];
  31.  
  32. vector<int> ne[MAX];
  33. int hash[MAX];
  34.  
  35. int top=0;
  36. int que[MAX];
  37.  
  38. void dfs(int u)
  39. {
  40. 	int i;
  41. 	hash[u]=1;
  42. 	que[++top]=u;
  43. 	REP2(i,0,(int)ne[u].size())
  44. 	{
  45. 		int v=ne[u][i];
  46. 		if(!hash[v])
  47. 			dfs(v);
  48. 	}
  49. }
  50.  
  51. int Work(int i)
  52. {
  53. 	top=0;
  54. 	dfs(i);
  55. 	int j,ss=0;
  56. 	REP(j,2,top)
  57. 		if(x[ que[j] ] == x[ que[j-1] ] || y[ que[j] ] == y[ que[j-1] ] )
  58. 		{
  59. 			++ss;
  60. 			swap(x[que[j]],y[que[j]]);
  61. 		}
  62. 	return min(ss,top-ss);
  63. }
  64.  
  65. int main()
  66. {
  67. 	int i;
  68. 	scanf("%d",&n);
  69. 	REP(i,1,n)
  70. 		scanf("%d",&x[i]);
  71. 	REP(i,1,n)
  72. 		scanf("%d",&y[i]);
  73. 	REP(i,1,n)
  74. 	{
  75. 		if(x[i]==y[i])
  76. 			continue;
  77. 		if(p1[x[i]])
  78. 			p2[x[i]]=i;
  79. 		else p1[x[i]]=i;
  80.  
  81. 		if(p1[y[i]])
  82. 			p2[y[i]]=i;
  83. 		else p1[y[i]]=i;
  84.  
  85. 		num[x[i]]++;
  86. 		num[y[i]]++;
  87. 	}
  88. 	REP(i,1,100000)
  89. 		if(p1[i] && p2[i])
  90. 		{
  91. 			ne[p1[i]].pb(p2[i]);
  92. 			ne[p2[i]].pb(p1[i]);
  93. 		}
  94. 	int ans=0;
  95. 	REP(i,1,100000)
  96. 		if(num[i]==1 && !hash[p1[i]])
  97. 			ans+=Work(p1[i]);
  98. 	REP(i,1,n)
  99. 	{
  100. 		if(x[i]==y[i])
  101. 			continue;
  102. 		if(hash[i])
  103. 			continue;
  104. 		ans+=Work(i);
  105. 	}
  106. 	cout<<ans<<endl;
  107. 	return 0;
  108. }
Success #stdin #stdout 0s 11160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/aNQTaN
language:
C++ (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!