fork download
  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.15s 20432KB
stdin
Standard input is empty
stdout