fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6. #define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
  7. #define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
  8. #define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
  9. #define rep(i, c) for(auto &(i) : (c))
  10. #define x first
  11. #define y second
  12. #define pb push_back
  13. #define PB pop_back()
  14. #define iOS ios_base::sync_with_stdio(false)
  15. #define sqr(a) (((a) * (a)))
  16. #define all(a) a.begin() , a.end()
  17. #define error(x) cerr << #x << " = " << (x) <<endl
  18. #define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
  19. #define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
  20. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  21. #define L(x) ((x)<<1)
  22. #define R(x) (((x)<<1)+1)
  23. #define umap unordered_map
  24. #define double long double
  25. typedef long long ll;
  26. typedef pair<int,int>pii;
  27. typedef vector<int> vi;
  28. typedef complex<double> point;
  29. template <typename T> using os =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  30. template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}
  31. template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}
  32. const int maxn = 2e5 + 10;
  33. vi adj[maxn * 2];
  34. int x[maxn * 2];
  35. map <pii, int> mp;
  36. map <pii, bool> del;
  37. vector<int> eu;
  38. set<int> d[2];
  39. int deg[maxn * 2];
  40. vector<pii> edges;
  41. inline void euler(int v){
  42. 	while(!adj[v].empty()){
  43. 		int u = adj[v].back();
  44. 		adj[v].PB;
  45. 		if(!del[{v, u}]){
  46. 			del[{v, u}] = del[{u, v}] = true;
  47. 			euler(u);
  48. 		}
  49. 	}
  50. 	eu.pb(v);
  51. }
  52. inline void deledge(int v,int u){
  53. 	del[{v, u}] = true;
  54. 	del[{u, v}] = true;
  55. 	d[deg[v]].erase(v);
  56. 	deg[v] = !deg[v];
  57. 	d[deg[v]].insert(v);
  58. 	d[deg[u]].erase(u);
  59. 	deg[u] = !deg[u];
  60. 	d[deg[u]].insert(u);
  61. }
  62. inline void solve(){
  63. 	if(d[1].empty()){
  64. 		For(i,0,maxn * 2){
  65. 			eu.clear();
  66. 			euler(i);
  67. 			For(j,1,eu.size())
  68. 				mp[{eu[j], eu[j-1]}] = mp[{eu[j-1], eu[j]}] = j % 2;
  69. 		}
  70. 	}
  71. 	else{
  72. 		int v = *d[1].begin();
  73. 		while(!adj[v].empty() && del[{v, adj[v].back()}])
  74. 			adj[v].PB;
  75. 		int u = adj[v].back();
  76. 		deledge(v, u);
  77. 		solve();
  78. 		int c = 0;
  79. 		if(x[u] > 0)
  80. 			c = 1;
  81. 		if(c == 1)
  82. 			x[u] --, x[v] --;
  83. 		else
  84. 			x[u] ++, x[v] ++;
  85. 		mp[{v, u}] = mp[{u, v}] = c;
  86. 	}
  87. }
  88. int n;
  89. string s = "rb";
  90. int main(){
  91. 	scanf("%d", &n);
  92. 	For(i,0,n){
  93. 		int x, y;
  94. 		scanf("%d %d", &x, &y);
  95. 		-- x, -- y;
  96. 		x = 2 * x + 1;
  97. 		y = 2 * y;
  98. 		edges.pb({x, y});
  99. 		adj[x].pb(y);
  100. 		adj[y].pb(x);
  101. 	}
  102. 	For(i,0,2*maxn)
  103. 		d[(int)adj[i].size() % 2].insert(i), deg[i] = adj[i].size() % 2;
  104. 	solve();
  105. 	rep(e, edges)
  106. 		printf("%c", (char)s[mp[{e.x, e.y}]]);
  107. 	puts("");
  108. }
  109.  
  110.  
Success #stdin #stdout 0.1s 34924KB
comments (?)
stdin
copy 
4
1 1
1 2
2 1
2 2
stdout
copy 
brrb
https://ideone.com/6h9FTM
language:
C++14 (gcc 8.3)
created:
2 days 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!