fork download
copy 
  1. // Forgotten tree (H), by Errichto
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
  5. #define RI(i,n) FOR(i,1,(n))
  6. #define REP(i,n) FOR(i,0,(n)-1)
  7.  
  8. char sl[10];
  9. int e[10][10], e_memo[10][10];
  10. vector<int> group[10];
  11. int boss[10];
  12.  
  13. typedef vector<pair<int,int>> Tree;
  14.  
  15. vector<int> w[10];
  16. bool vis[10];
  17. void dfs(int a) {
  18. 	vis[a] = true;
  19. 	for(int b : w[a]) if(!vis[b]) dfs(b);
  20. }
  21. bool validTree(Tree t, int k) {
  22. 	for(pair<int,int> edge : t) {
  23. 		w[edge.first].push_back(edge.second);
  24. 		w[edge.second].push_back(edge.first);
  25. 	}
  26. 	dfs(1);
  27. 	bool ans = true;
  28. 	RI(i, k) if(!vis[i]) ans = false;
  29. 	RI(i, k) vis[i] = false;
  30. 	RI(i, k) w[i].clear();
  31. 	return ans;
  32. }
  33.  
  34. bool checkEverything(int k) { // O(k * 2^k)
  35. 	REP(mask, (1 << k)) {
  36. 		vector<int> subset;
  37. 		REP(i, k) if(mask & (1 << i)) subset.push_back(i + 1);
  38. 		int vertices = 0, edges = 0;
  39. 		for(int i : subset) vertices += group[i].size() - 1;
  40. 		for(int i : subset) for(int j : subset) edges += e[i][j];
  41. 		if(edges > vertices) return false;
  42. 	}
  43. 	return true;
  44. }
  45.  
  46. void write(Tree t) {
  47. 	for(pair<int,int> edge : t) printf("%d-%d\n", edge.first, edge.second);
  48. 	puts("");
  49. }
  50.  
  51. void tryTree(Tree t, int k) {
  52. 	RI(i, k) RI(j, k) e[i][j] = e_memo[i][j];
  53. 	for(pair<int,int> p : t) {
  54. 		int & tmp = e[p.first][p.second];
  55. 		if(tmp == 0) return;
  56. 		--tmp;
  57. 	}
  58. 	if(!checkEverything(k)) return;
  59. 	vector<pair<int,int>> ans;
  60. 	for(pair<int,int> p : t) ans.push_back({boss[p.first], boss[p.second]}); //
  61. 	RI(i, k) RI(j, k) while(e[i][j]) {
  62. 		--e[i][j];
  63. 		if((int) group[i].size() > 1) {
  64. 			int memo = group[i].back();
  65. 			group[i].pop_back();
  66. 			if(checkEverything(k)) {
  67. 				ans.push_back({boss[j], memo});
  68. 				// printf("%d %d\n", boss[j], group[i].back());
  69. 				continue;
  70. 			}
  71. 			group[i].push_back(memo);
  72. 		}
  73. 		assert((int) group[j].size() > 1);
  74. 		ans.push_back({boss[i], group[j].back()});
  75. 		// printf("%d %d\n", boss[i], group[j].back());
  76. 		group[j].pop_back();
  77. 		assert(checkEverything(k));
  78. 	}
  79. 	RI(i, k) assert((int) group[i].size() == 1);
  80. 	random_shuffle(ans.begin(), ans.end());
  81. 	for(pair<int,int> p : ans) {
  82. 		if(rand()%2) swap(p.first, p.second);
  83. 		printf("%d %d\n", p.first, p.second);
  84. 	}
  85. 	exit(0);
  86. }
  87.  
  88. vector<Tree> findTrees(int k) {
  89. 	vector<Tree> ans;
  90. 	vector<pair<int,int>> edges;
  91. 	RI(i, k) FOR(j, i+1, k) edges.push_back({i, j});
  92. 	REP(mask, (1 << edges.size())) if(__builtin_popcount(mask) == k - 1) {
  93. 		Tree t;
  94. 		REP(i, (int) edges.size()) if(mask & (1 << i)) t.push_back(edges[i]);
  95. 		if(validTree(t, k)) ans.push_back(t);
  96. 	}
  97. 	return ans;
  98. }
  99.  
  100. int findLog(int n) {
  101. 	int k = 0;
  102. 	while(n) {
  103. 		++k;
  104. 		n /= 10;
  105. 	}
  106. 	return k;
  107. }
  108.  
  109. int main() {
  110. 	srand(42);
  111. 	int n;
  112. 	scanf("%d", &n);
  113. 	RI(i, n) group[findLog(i)].push_back(i);
  114. 	REP(_, n - 1) {
  115. 		scanf("%s", sl);
  116. 		int a = strlen(sl);
  117. 		scanf("%s", sl);
  118. 		int b = strlen(sl);
  119. 		if(a > b) swap(a, b);
  120. 		++e[a][b];
  121. 	}
  122. 	int k = findLog(n);
  123. 	RI(i, k) boss[i] = group[i][0];
  124. 	RI(i, k) RI(j, k) e_memo[i][j] = e[i][j];
  125. 	vector<Tree> trees = findTrees(k);
  126. 	for(Tree t : trees) tryTree(t, k);
  127. 	puts("-1");
  128. 	return 0;
  129. }
Success #stdin #stdout 0s 3424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/7KuS1l
Tree
language:
C++14 (gcc 8.3)
created:
8 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!