fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. using namespace std;
  5. const int MAX = 400005;
  6. vector<int> adj[MAX];
  7. map<int, int> mpx, mpy;
  8. map<pair<int, int>, int> ind;
  9. int from[MAX], to[MAX], ptr[MAX];
  10. bool mark[MAX], seen[MAX];
  11. int cntx, cnty;
  12. vector<int> ver;
  13. char ans[MAX];
  14. void dfs(int v)
  15. {
  16. 	seen[v] = true;
  17. 	while (ptr[v] < adj[v].size())
  18. 	{
  19. 		int id = adj[v][ptr[v]++];
  20. 		int u = from[id] + to[id] - v;
  21. 		if (!mark[id])
  22. 		{
  23. 			mark[id] = true;
  24. 			dfs(u);
  25. 		}
  26. 	}
  27. 	ver.push_back(v);
  28. }
  29. int main()
  30. {
  31. 	ios::sync_with_stdio(false);
  32. 	int n;
  33. 	cin >> n;
  34. 	for (int i = 0; i < n; i++)
  35. 	{
  36. 		int x, y;
  37. 		cin >> x >> y;
  38. 		if (!mpx.count(x))
  39. 			mpx[x] = cntx++;
  40. 		if (!mpy.count(y))
  41. 			mpy[y] = cnty++;
  42. 		from[i] = mpx[x];
  43. 		to[i] = mpy[y] + n;
  44. 		ind[make_pair(from[i], to[i])] = i;
  45. 		ind[make_pair(to[i], from[i])] = i;
  46. 		adj[from[i]].push_back(i);
  47. 		adj[to[i]].push_back(i);
  48. 	}
  49. 	int m = n;
  50. 	for (int i = 0; i < 2 * n; i++)
  51. 		if (adj[i].size() & 1)
  52. 		{
  53. 			from[m] = i;
  54. 			to[m] = MAX - 1;
  55. 			if (i >= n)
  56. 				to[m]--;
  57. 			adj[from[m]].push_back(m);
  58. 			adj[to[m]].push_back(m);
  59. 			m++;
  60. 		}
  61. 	if (adj[MAX - 1].size() & 1)
  62. 		dfs(MAX - 1);
  63. 	if ((adj[MAX - 2].size() & 1) && !mark[MAX - 2])
  64. 		dfs(MAX - 2);
  65. 	for (int i = 0; i < cntx; i++)
  66. 		if (!seen[i] && (adj[i].size() & 1))
  67. 			dfs(i);
  68. 	for (int i = 0; i < cntx; i++)
  69. 		if (!seen[i])
  70. 			dfs(i);
  71. 	for (int i = 0; i + 1 < ver.size(); i++)
  72. 		if (ind.count(make_pair(ver[i], ver[i + 1])))
  73. 		{
  74. 			if (i & 1)
  75. 				ans[ind[make_pair(ver[i], ver[i + 1])]] = 'r';
  76. 			else
  77. 				ans[ind[make_pair(ver[i], ver[i + 1])]] = 'b';
  78. 		}
  79. 	for (int i = 0; i < n; i++)
  80. 		cout << ans[i];
  81. 	cout << endl;
  82. 	return 0;
  83. }
  84.  
Runtime error #stdin #stdout 0s 13832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eL5XDx
language:
C++14 (gcc 8.3)
created:
9 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!