fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int N, P[20], res[20][20], dist[20][20], cnt; vector<int>G[20];
  7. bool used[20], iscenter[20], iscenterpass[20][20];
  8.  
  9. void init() {
  10. 	for (int i = 0; i < 20; i++) {
  11. 		for (int j = 0; j < 20; j++) {
  12. 			res[i][j] = 0; dist[i][j] = 0; iscenterpass[i][j] = false; cnt = 0;
  13. 		}
  14. 		G[i].clear(); used[i] = false; iscenter[i] = false;
  15. 	}
  16. }
  17.  
  18. void dfs(int pos) {
  19. 	cnt++;
  20. 	for (int i = 0; i < G[pos].size(); i++) {
  21. 		if (used[G[pos][i]] == true) continue;
  22. 		used[G[pos][i]] = true;
  23. 		dfs(G[pos][i]);
  24. 		used[G[pos][i]] = false;
  25. 	}
  26. }
  27.  
  28. void dfs2(int pos, int root, bool flag) {
  29. 	used[pos] = true; iscenterpass[root][pos] = flag;
  30. 	for (int i = 0; i < G[pos].size(); i++) {
  31. 		if (used[G[pos][i]] == true) continue;
  32. 		bool E = (flag | iscenter[G[pos][i]]);
  33. 		dfs2(G[pos][i], root, E);
  34. 	}
  35. }
  36.  
  37. int count_simple_path() {
  38. 	cnt = 0;
  39. 	for (int i = 1; i <= N; i++) {
  40. 		used[i] = true; dfs(i); used[i] = false; cnt--;
  41. 	}
  42. 	return cnt / 2;
  43. }
  44.  
  45. void dfs1(int pos, int root, int dep) {
  46. 	if (dist[root][pos] != (1 << 30)) return;
  47. 	dist[root][pos] = dep;
  48. 	for (int i = 0; i < G[pos].size(); i++) dfs1(G[pos][i], root, dep + 1);
  49. }
  50.  
  51. vector<int> get_center() {
  52. 	for (int i = 1; i <= N; i++) G[i].clear();
  53. 	for (int i = 2; i <= N; i++) { G[P[i]].push_back(i); G[i].push_back(P[i]); }
  54. 	for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) dist[i][j] = (1 << 30); }
  55. 	for (int i = 1; i <= N; i++) dfs1(i, i, 0);
  56.  
  57. 	int minx = (1 << 30);
  58. 	for (int i = 1; i <= N; i++) {
  59. 		int rem = 0;
  60. 		for (int j = 1; j <= N; j++) rem = max(rem, dist[i][j]);
  61. 		minx = min(minx, rem);
  62. 	}
  63.  
  64. 	vector<int>vec;
  65. 	for (int i = 1; i <= N; i++) {
  66. 		int rem = 0;
  67. 		for (int j = 1; j <= N; j++) rem = max(rem, dist[i][j]);
  68. 		if (rem == minx) vec.push_back(i);
  69. 	}
  70. 	return vec;
  71. }
  72.  
  73. pair<int, int> solve() {
  74. 	vector<int> centroid = get_center(); for (int i = 0; i < centroid.size(); i++) iscenter[centroid[i]] = true;
  75. 	for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) used[j] = false; dfs2(i, i, iscenter[i]); }
  76.  
  77. 	int maxn = 0, maxn2 = 0;
  78. 	for (int i = 1; i <= N; i++) {
  79. 		for (int j = i + 1; j <= N; j++) {
  80. 			for (int k = 0; k <= N; k++) G[k].clear();
  81. 			for (int k = 2; k <= N; k++) { G[P[k]].push_back(k); G[k].push_back(P[k]); }
  82. 			G[i].push_back(j); G[j].push_back(i);
  83.  
  84. 			res[i][j] = count_simple_path();
  85. 			res[j][i] = res[i][j];
  86. 			maxn = max(maxn, res[i][j]);
  87. 			if (iscenterpass[i][j] == true) maxn2 = max(maxn2, res[i][j]);
  88. 		}
  89. 	}
  90. 	return make_pair(maxn, maxn2);
  91. }
  92.  
  93. int cntv = 0, cntw = 0;
  94.  
  95. void dfs_solve(int dep) {
  96. 	if (dep == N + 1) {
  97. 		init(); cntw++;
  98. 		pair<int, int> E = solve();
  99. 		if (E.first != E.second) {
  100. 			cntv++;
  101. 			cout << "Case " << cntv << ":" << endl;
  102. 			cout << N << endl;
  103. 			for (int j = 2; j <= N; j++) cout << P[j] << " " << j << endl;
  104. 			cout << endl;
  105. 		}
  106. 		return;
  107. 	}
  108. 	for (int j = 1; j < dep; j++) {
  109. 		P[dep] = j;
  110. 		dfs_solve(dep + 1);
  111. 	}
  112. }
  113.  
  114. int main() {
  115. 	cin >> N;
  116. 	dfs_solve(2);
  117. 	cout << cntv << " out of " << cntw << " cases were counter-example" << endl;
  118. 	return 0;
  119. }
Success #stdin #stdout 0.17s 15248KB
comments (?)
stdin
copy 
8
stdout
copy 
0 out of 5040 cases were counter-example
https://ideone.com/4jC4SV
language:
C++14 (gcc 8.3)
created:
4 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!