fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N = 2e5 + 5;
  5. int c, n, e;
  6. int grid[2][N];
  7. vector<vector<int> > g;
  8. int at;
  9. int parent[N];
  10. void BFS(int u) {
  11. 	queue<int> q;
  12. 	memset(parent, -1, sizeof(parent));
  13. 	q.push(u);
  14. 	parent[u] = -2;
  15. 	while (!q.empty()) {
  16. 		u = q.front();
  17. 		q.pop();
  18. 		for (auto &v : g[u])
  19. 			if (parent[v] == -1) {
  20. 				parent[v] = u;
  21. 				q.push(v);
  22. 			}
  23. 	}
  24. 	at = u;
  25. }
  26. int hasOtherCommon(int u, int v, int than) {
  27. 	set<int> s(g[u].begin(), g[u].end());
  28. 	s.erase(than);
  29. 	for (auto &x : g[v])
  30. 		if (s.find(x) != s.end())
  31. 			return x;
  32. 	return -1;
  33. }
  34. vector<pair<int, int> > loc;
  35. void updateColumn(int i, bool flip, int shift) {
  36. 	if (grid[0][i] != -1) {
  37. 		loc[grid[0][i]].first ^= flip;
  38. 		loc[grid[0][i]].second -= shift;
  39. 	}
  40. 	if (grid[1][i] != -1) {
  41. 		loc[grid[1][i]].first ^= flip;
  42. 		loc[grid[1][i]].second -= shift;
  43. 	}
  44. }
  45. void print() {
  46. 	memset(grid, -1, sizeof(grid));
  47. 	int minCol = n;
  48. 	for (int i = 0; i < n; ++i)
  49. 		minCol = min(minCol, loc[i].second);
  50. 	for (int i = 0; i < n; ++i)
  51. 		grid[loc[i].first][loc[i].second - minCol] = i;
  52. 	for (int i = 0; i < 2; ++i, puts(""))
  53. 		for (int j = 0; j < c; ++j)
  54. 			printf("%d ", grid[i][j] + 1);
  55. }
  56. int main() {
  57. 	scanf("%d%d%d", &c, &n, &e);
  58. 	g.resize(n);
  59. 	for (int i = 0, a, b; i < e; ++i) {
  60. 		scanf("%d%d", &a, &b);
  61. 		--a; --b;
  62. 		g[a].push_back(b);
  63. 		g[b].push_back(a);
  64. 	}
  65. 	for (auto &v : g) {
  66. 		sort(v.begin(), v.end(), [&](const int &a, const int &b) {
  67. 			return g[a].size() < g[b].size();
  68. 		});
  69. 	}
  70. 	BFS(0);
  71. 	int e1 = at;
  72. 	BFS(at);
  73. 	int e2 = at;
  74. 	vector<int> path;
  75. 	int cur = e2;
  76. 	while (cur != -2) {
  77. 		path.push_back(cur);
  78. 		cur = parent[cur];
  79. 	}
  80. 	reverse(path.begin(), path.end());
  81. 	loc.resize(n, make_pair(-1, -1));
  82. 	memset(grid, -1, sizeof(grid));
  83. 	if (path.size() == n) {
  84. 		grid[0][0] = path[0];
  85. 		loc[path[0]] = { 0,0 };
  86. 		int r = 1, c = 0;
  87. 		for (int j = 1; j < path.size(); ++j) {
  88. 			grid[r][c] = path[j];
  89. 			loc[path[j]] = { r,c };
  90. 			if (c % 2 == 0 && grid[!r][c] == -1)
  91. 				r = !r;
  92. 			else
  93. 				++c;
  94. 		}
  95. 		print();
  96. 		return 0;
  97. 	}
  98. 	loc[path[0]] = { 0,0 };
  99. 	grid[0][0] = path[0];
  100. 	int r = 0, c = 1;
  101. 	for (int i = 1; i + 1 < path.size(); ++i) {
  102. 		int ret = hasOtherCommon(path[i - 1], path[i + 1], path[i]);
  103. 		if (ret != -1) {
  104. 			r = !r;
  105. 			--c;
  106. 		}
  107. 		loc[path[i]] = { r,c };
  108. 		grid[r][c] = path[i];
  109. 		++c;
  110. 		if (ret != -1) {
  111. 			loc[ret] = { !r,c };
  112. 			grid[!r][c] = ret;
  113. 		}
  114. 	}
  115. 	loc[path.back()] = { r,c };
  116. 	grid[r][c] = path.back();
  117. 	for (int c = 0; c < n; ++c)
  118. 		for (int r = 0; r < 2; ++r)
  119. 			if (grid[r][c] != -1) {
  120. 				if (grid[!r][c] != -1)
  121. 					continue;
  122. 				bool found = false;
  123. 				for (auto &x : g[grid[r][c]])
  124. 					if (loc[x].first == -1) {
  125. 						loc[x] = { !r,c };
  126. 						grid[!r][c] = x;
  127. 						found = true;
  128. 						break;
  129. 					}
  130. 				if (found)
  131. 					break;
  132. 			}
  133. 	int prefix = -1;
  134. 	for (int i = 0; i < n; ++i) {
  135. 		if (grid[0][i] != -1 && grid[1][i] != -1) {
  136. 			prefix = i - 1;
  137. 			break;
  138. 		}
  139. 	}
  140. 	int sum = 0;
  141. 	bool flip = false;
  142. 	int shift = 0;
  143. 	int lastIdx;
  144. 	for (int i = prefix + 1; i < n; ++i) {
  145. 		updateColumn(i, flip, shift);
  146. 		if (grid[0][i] == -1 && grid[1][i] == -1)
  147. 			break;
  148. 		if (grid[0][i] != -1 && grid[1][i] != -1) {
  149. 			sum = 0;
  150. 			continue;
  151. 		}
  152. 		++sum;
  153. 		if (sum == 4) {
  154. 			++shift;
  155. 			flip ^= 1;
  156. 			updateColumn(i, true, 1);
  157. 			updateColumn(i - 1, true, 1);
  158. 			sum = 1;
  159. 		}
  160. 		if (grid[0][i] != -1)
  161. 			lastIdx = grid[0][i];
  162. 		else if (grid[1][i] != -1)
  163. 			lastIdx = grid[1][i];
  164. 	}
  165. 	if (sum >= 3) {
  166. 		loc[lastIdx].first ^= 1;
  167. 		--loc[lastIdx].second;
  168. 	}
  169. 	sum = 0;
  170. 	flip = false;
  171. 	shift = 0;
  172. 	for (int i = prefix; i >= 0; --i) {
  173. 		updateColumn(i, flip, shift);
  174. 		if (grid[0][i] == -1 && grid[1][i] == -1)
  175. 			break;
  176. 		if (grid[0][i] != -1 && grid[1][i] != -1) {
  177. 			sum = 0;
  178. 			continue;
  179. 		}
  180. 		++sum;
  181. 		if (sum == 4) {
  182. 			--shift;
  183. 			flip ^= 1;
  184. 			updateColumn(i, true, -1);
  185. 			updateColumn(i + 1, true, -1);
  186. 			sum = 1;
  187. 		}
  188. 		if (grid[0][i] != -1)
  189. 			lastIdx = grid[0][i];
  190. 		else if (grid[1][i] != -1)
  191. 			lastIdx = grid[1][i];
  192. 	}
  193. 	if (sum >= 3) {
  194. 		loc[lastIdx].first ^= 1;
  195. 		++loc[lastIdx].second;
  196. 	}
  197. 	print();
  198. 	return 0;
  199. }
Success #stdin #stdout 0s 17592KB
comments (?)
stdin
copy 
7 10 10
2 10
7 4
10 3
1 4
3 9
9 6
1 6
5 4
6 8
8 3
stdout
copy 
2 10 3 8 0 7 0 
0 0 9 6 1 4 5
https://ideone.com/Y0GjEk
language:
C++ (gcc 8.3)
created:
4 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!