fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include "bits/stdc++.h"
  3. #include "ext/pb_ds/assoc_container.hpp"
  4. #include "ext/pb_ds/tree_policy.hpp"
  5. using namespace __gnu_pbds;
  6. using namespace std;
  7. typedef long long int ll;
  8. // #define int long long int
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define deb cerr << "Line no." << __LINE__
  13. #define fr(i, a, b) for(int i = a; i <= b; i++)
  14. #define all(x) x.begin(), x.end()
  15. #define IO ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
  16. #define pii pair<int,int>
  17. #define sz(x) (int)x.size()
  18. const int mod = 1e9 + 7;
  19. const int mod1 = 998244353;
  20. typedef double f80;
  21. #ifndef LOCAL
  22. #define endl '\n'
  23. #endif
  24.  
  25. template<typename T>
  26. using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
  27.  
  28. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  29. int rand(int l, int r){
  30. 	uniform_int_distribution<int> uid(l, r);
  31. 	return uid(rng);
  32. }
  33. int pwr(int a,int b){
  34. 	int ans = 1;
  35. 	while(b){
  36. 		if(b & 1) ans = (ans * a) % mod;
  37. 		a = (a * a) % mod;
  38. 		b >>= 1;
  39. 	}
  40. 	return ans;
  41. }
  42. class cmp
  43. {
  44. public:
  45. 	inline bool operator () (const pair<int,vector<char>> &a, const pair<int,vector<char>> &b){
  46. 		return a.fi > b.fi;
  47. 	}
  48. };
  49. class cmp1
  50. {
  51. public:
  52. 	inline bool operator () (const pair<pii,vector<char>> &a, const pair<pii,vector<char>> &b){
  53. 		return a.fi.fi + a.fi.se > b.fi.fi + b.fi.se;
  54. 	}
  55. };
  56. priority_queue<pair<int,vector<char>>,vector<pair<int,vector<char>>>,cmp> q; 
  57. priority_queue<pair<pii,vector<char>>,vector<pair<pii,vector<char>>>,cmp1> q1;
  58. vector<pii> moves;
  59. bool check(vector<char> &v){
  60. 	fr(i, 0, sz(v) - 1){
  61. 		if(v[i] != i + 1) return 0;
  62. 	}
  63. 	return 1;
  64. }
  65. int dp[15][15];
  66. map<ll,int> dist2, dist;
  67. queue<vector<char>> qu;
  68. ll hh(vector<char> &v){
  69. 	ll h = 0;
  70. 	for(char ch : v){
  71. 		h = (h * 119 + ch) % mod;
  72. 	}
  73. 	return h;
  74. }
  75. int good_approx(vector<char> v){
  76. 	int n = sz(v);
  77. 	ll h1 = hh(v);
  78. 	q.push({0, v});
  79. 	dist2[h1] = 0;
  80. 	while(!q.empty()){
  81. 		auto y = q.top();
  82. 		q.pop();
  83. 		auto v = y.se;
  84. 		ll h1 = hh(v);
  85. 		int d = y.fi;
  86. 		if(y.fi > dist2[h1]) continue;
  87. 		if(check(v)) return d;
  88. 		fr(i, 0, n - 1){
  89. 			fr(j, 0, n - 1){
  90. 				if(i == j) continue;
  91. 				if(dp[i][j] == 1e9) continue;
  92. 				int dd = d + 2 * dp[i][j] - 1;
  93. 				if(v[i] == i + 1 && v[j] == j + 1) continue;
  94. 				if(v[i] == j + 1 || v[j] == i + 1){
  95. 					swap(v[i], v[j]);
  96. 					ll h1 = hh(v);
  97. 					if(!dist2.count(h1) || dist2[h1] > dd)
  98. 						dist2[h1] = dd, q.push({dd, v});
  99. 					swap(v[i], v[j]);
  100. 				}
  101. 			}
  102. 		}
  103. 	}
  104. }
  105. int h_value(vector<char> &v){ // minimum number of moves to make the permutation identity permutation
  106. 	int ret = 0;
  107. 	fr(i, 0, sz(v) - 1){
  108. 		ret += (v[i] != i + 1);
  109. 	}
  110. 	return (ret + 1) / 2;
  111. }
  112. vector<int> rev;
  113. void solve(vector<char> v,int cutoff){
  114. 	ll h1 = hh(v);
  115. 	q1.push({{0, dist[h1] = h_value(v)}, v});
  116. 	while(!q1.empty()){
  117. 		auto u = q1.top();
  118. 		q1.pop();
  119. 		auto v = u.se;
  120. 		ll h1 = hh(v);
  121. 		int d = u.fi.fi;
  122. 		if(dist[h1] < u.fi.fi + u.fi.se) continue;
  123. 		if(check(v)){
  124. 			cout << d << endl;
  125. 			return;
  126. 		}
  127. 		int c = 0;
  128. 		for(pii x : moves){
  129. 			c++;
  130. 			swap(v[x.fi], v[x.se]);
  131. 			ll h1 = hh(v);
  132. 			int h = h_value(v);
  133. 			int f = h + d + 1;
  134. 			if(f <= cutoff)
  135. 				if(!dist.count(h1) || dist[h1] > f){
  136. 					dist[h1] = f;
  137. 					q1.push({{d + 1, h}, v});
  138. 				}
  139. 			swap(v[x.fi], v[x.se]);
  140. 		}
  141. 	}
  142. 	assert(0);
  143. }
  144. void solve(){
  145. 	int n, m;
  146. 	cin >> n >> m;
  147. 	vector<char> v;
  148. 	fr(i, 1, n){
  149. 		int x;
  150. 		cin >> x;
  151. 		v.pb(x);
  152. 	}
  153. 	fr(i, 0, n - 1){
  154. 		fr(j, 0, n - 1){
  155. 			if(i == j) dp[i][j] = 0;
  156. 			else dp[i][j] = 1e9;
  157. 		}
  158. 	}
  159. 	fr(i, 1, m){
  160. 		int x, y;
  161. 		cin >> x >> y;
  162. 		x--, y--;
  163. 		if(x > y) swap(x, y);
  164. 		dp[x][y] = dp[y][x] = 1;
  165. 		moves.pb({x, y});
  166. 	}
  167. 	fr(k, 0, n - 1){
  168. 		fr(i, 0, n - 1){
  169. 			fr(j, 0, n - 1){
  170. 				if(dp[i][k] + dp[k][j] < dp[i][j])
  171. 					dp[i][j] = dp[i][k] + dp[k][j];
  172. 			}
  173. 		}
  174. 	}
  175. 	int d = good_approx(v);
  176. 	// int d1 = exact(v);
  177. 	solve(v, d);
  178. }
  179. signed main(){
  180.   	IO;
  181.   	#ifdef LOCAL
  182. 		freopen("inp.txt","r", stdin);
  183. 		// freopen("out.txt", "w", stdout);
  184. 	#endif
  185. 	clock_t clk = clock();
  186.   	int t = 1;
  187.   	// cin >> t;
  188.   	fr(tt, 1, t){
  189.     	solve();
  190.   	}
  191.   	cerr << endl << (double)(clock() - clk) / CLOCKS_PER_SEC;
  192.   	return 0;
  193. }
Success #stdin #stdout #stderr 0s 15400KB
comments (?)
stdin
copy 
5 4
5 4 3 2 1
1 2
2 3
3 4
4 5
stdout
copy 
10
stderr
copy 
0.0001
https://ideone.com/93uJrO
language:
C++14 (gcc 8.3)
created:
5 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!