fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <math.h>
  3. using namespace std;
  4. #define ll long long int
  5. ll mod=998244353;
  6. ll mul(ll a,ll b)
  7. {
  8.     return ((a%mod)*(b%mod))%mod;
  9. }
  10. ll add(ll a,ll b)
  11. {
  12.     return ((a%mod)+(b%mod))%mod;
  13. }
  14. ll sub(ll a,ll b)
  15. {
  16.     return (((a+mod)%mod)-((b+mod)%mod)+mod)%mod;
  17. }
  18. ll po(ll a, ll b)
  19. {
  20.     if(b==0)
  21.     {
  22.         return 1;
  23.     }
  24.     ll t=po(a,b/2);
  25.     if(b%2)
  26.     {
  27.         return mul(t,mul(t,a));
  28.     }
  29.     else
  30.     {
  31.         return mul(t,t);
  32.     }
  33. }
  34. ll fen[300005];
  35. void upd(ll x, ll n)
  36. {
  37. 	for(ll i=x;i<=n;i+=(i&(-i)))
  38. 	{
  39. 		fen[i]++;
  40. 	}
  41. }
  42. ll ret(ll x)
  43. {
  44. 	ll out=0;
  45. 	for(ll i=x;i>0;i-=(i&(-i)))
  46. 	{
  47. 		out+=fen[i];
  48. 	}
  49. 	return out;
  50. }
  51. vector<ll> v[100005];
  52. int main()
  53. {
  54. 	ios_base::sync_with_stdio(false);
  55. 	cin.tie(NULL);
  56. 	cout.tie(NULL);
  57. 	cout<<fixed<<setprecision(12);
  58. 	ll t;
  59. 	cin>>t;
  60. 	while(t--)
  61. 	{
  62. 		ll n;
  63. 		cin>>n;
  64. 		for(ll i=0;i<n+3;i++)
  65. 		{
  66. 			v[i].clear();
  67. 		}
  68.  
  69. 		ll a[n];
  70. 		unordered_map<ll,ll> m1;
  71. 		for(ll i=0;i<n;i++)
  72. 		{
  73. 			cin>>a[i];
  74. 			a[i]--;
  75. 			v[i].push_back(a[i]);
  76. 			m1[a[i]]++;
  77. 		}
  78. 		ll c[n];
  79. 		set<pair<ll,ll>> s1;
  80. 		for(ll i=0;i<n;i++)
  81. 		{
  82. 			cin>>c[i];
  83. 			s1.insert(make_pair(c[i],i));
  84. 		}
  85. 		queue<ll> q;
  86. 		for(ll i=0;i<n;i++)
  87. 		{
  88. 			if(m1[i]==0)
  89. 			{
  90. 				q.push(i);
  91. 			}
  92. 		}
  93. 		ll out=0;
  94. 		while(q.size())
  95. 		{
  96. 			auto it = q.front();
  97. 			q.pop();
  98. 			out+=(2*c[it]);
  99. 			m1[a[it]]--;
  100. 			if(m1[a[it]]==0)
  101. 			{
  102. 				q.push(a[it]);
  103. 			}
  104. 			auto it1 = s1.find(make_pair(c[it],it));
  105. 			s1.erase(it1);
  106. 		}
  107. 		for(auto i:s1)
  108. 					{
  109. 						cout<<i.first<<" "<<i.second<<"\n";
  110. 					}
  111. 		while(s1.size())
  112. 		{
  113. 			auto it =s1.begin();
  114. 			pair<ll,ll> p =(*it);
  115. 			s1.erase(it);
  116. 			ll ss = a[p.second];
  117. 			while(ss!=p.second)
  118. 			{
  119. 				out+=(2*c[ss]);
  120. 				auto it1 = s1.find(make_pair(c[ss],ss));
  121. 				s1.erase(it1);
  122. 				ss = a[ss];
  123.  
  124. 			}
  125.  
  126. 			out+=p.first;
  127. 		}
  128. 		cout<<out<<"\n";
  129. 	}
  130. 	return 0;
  131. }
Success #stdin #stdout 0.01s 6128KB
comments (?)
stdin
copy 
1
3
2 3 2
6 6 1
8
2 1 4 3 6 5 8 7
1 2 1 2 2 1 2 1
5
2 1 1 1 1
9 8 1 1 1
2
2 1
1000000000 999999999
7
2 3 2 6 4 4 3
1 2 3 4 5 6 7
5
3 4 4 1 3
3 4 5 6 7
3
2 1 1
1 2 2
4
2 1 4 1
1 1 1 1
stdout
copy 
1 2
6 1
25
https://ideone.com/ogBBkk
language:
C++14 (gcc 8.3)
created:
21 days 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!