daily pastebin goal
28%
SHARE
TWEET

Untitled

a guest Feb 23rd, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define all(x) (x).begin(), (x).end()
  5.  
  6. #define TRACE(x) x
  7. #define WATCH(x) TRACE(cout << #x" = " << x << endl)
  8. #define PRINT(x...) TRACE(printf(x))
  9. #define WATCHR(a, b) TRACE(for (auto c=a; c!=b;) cout << *(c++) << " "; cout << endl)
  10. #define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})
  11.  
  12. #define FU(i, a, b) for (auto i = a; i < b; ++i)
  13. #define fu(i, b) FU(i, 0, b)
  14. #define FD(i, a, b) for (auto i = (b) - 1; i >= a; --i)
  15. #define fd(i, b) FD(i, 0, b)
  16. #define sz(x) (int) (x).size()
  17. #define pb push_back
  18.  
  19. using ll = long long;
  20. using vi = vector<int>;
  21. using vvi = vector<vi>;
  22. using vll = vector<ll>;
  23. using vvll = vector<vll>;
  24. using vd = vector<double>;
  25. using vb = vector<bool>;
  26. using pii = pair<int, int>;
  27. using pll = pair<ll, ll>;
  28.  
  29. ll mod(ll a, ll b) {
  30.   return ((a%b)+b)%b;
  31. }
  32.  
  33. int cmp(double x, double y = 0, double tol = 1.e-7) {
  34.     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  35. }
  36.  
  37.  
  38. struct graph {
  39.   //////////////////////////////////////////////////////////////////////////////
  40.   // Shared part. Also known as: You will need this!
  41.   //
  42.   vi dest;  // use sz(dest) as nar
  43.   vvi adj;  // use sz(adj) as nvt
  44.   int inv(int a) { return a ^ 0x1; }
  45.   graph(int n = 0) {
  46.     adj.resize(n);
  47.   }
  48.   // Adds an arc to the graph. u is capacity, c is cost.
  49.   // u is only needed on flows, and c only on min-cost-flow
  50.   int arc(int i, int j) {
  51.     dest.pb(j);
  52.     adj[i].pb(sz(dest)-1);
  53.     dest.pb(i);
  54.     adj[j].pb(sz(dest)-1);
  55.     return sz(dest)-2;
  56.   }
  57.  
  58.   //////////////////////////////////////////////////////////////////////////////
  59.   // Both Bridges/Articulation points and to Strongly Connected Components
  60.   //
  61.  
  62.   vi depth;
  63.  
  64.    
  65.  
  66.   //////////////////////////////////////////////////////////////////////////////
  67.   // Strongly Connected Components - O(n+m)
  68.   // see [rep] for results
  69.   //
  70.  
  71.   vi ord, rep;
  72.  
  73.   int transp(int a) { return (a & 0x1); }
  74.  
  75.   void dfs_topsort(int u) {
  76.         for (int a : adj[u]) {
  77.       int v = dest[a];
  78.       if (!transp(a) && depth[v] == -1) {
  79.         depth[v] = depth[u] + 1;
  80.         dfs_topsort(v);
  81.       }
  82.     }
  83.     ord.pb(u);
  84.   }
  85.  
  86.   void dfs_compfortcon(int u, int ent) {
  87.     rep[u] = ent;
  88.         for (int a : adj[u]) {
  89.       int v = dest[a];
  90.       if (transp(a) && rep[v] == -1) dfs_compfortcon(v, ent);
  91.     }
  92.   }
  93.  
  94.   void compfortcon() {
  95.     depth = vi(sz(adj), -1);
  96.     ord.clear();
  97.     fu(u, sz(adj)) if (depth[u] == -1) {
  98.         depth[u] = 0;
  99.         dfs_topsort(u);
  100.     }
  101.  
  102.     rep = vi(sz(adj), -1);
  103.     for (int i = sz(adj)-1, j = 0; i >= 0; i--) if (rep[ord[i]] == -1)
  104.       dfs_compfortcon(ord[i], j++);
  105.     reverse( ord.begin(), ord.end() );
  106.   }
  107.  
  108. };
  109.  
  110. int n, m;
  111. vector< pair<int, int> > edges;
  112. vector< vector<int> > secondGraph;
  113. vector<int> edgeColors;
  114.  
  115. // Estou lidando com intervalos semi-abertos!!!
  116. void recursiveMark(int start, int end, int color, const graph& GRAPH) {
  117.     vector<int> nodes;
  118.     vector<int> groups(n, -1);
  119.     int groupSize = (end - start) / 42 + 1;
  120.     for(int i = start; i < end; ++i) {
  121.         groups[ GRAPH.ord[i] ] = ( i - start ) / groupSize;
  122.     }
  123.     deque<bool> pendente( (end - start) / groupSize + 1, false);
  124.     for(int i = start; i < end; ++i) {
  125.         for(const auto& out : secondGraph[ GRAPH.ord[i] ] ) {
  126.             int dest = edges[out].second;
  127.             if( groups[dest] != groups[ GRAPH.ord[i] ] && edgeColors[out] == -1 && groups[ dest ] != -1) edgeColors[out] = color;
  128.             else if( groups[ GRAPH.ord[i] ] == groups[dest] ) pendente[ groups[GRAPH.ord[i]] ] = true;
  129.         }
  130.     }
  131.     for(int g = 0; g < (int) pendente.size(); ++g) {
  132.         if( pendente[g] ) {
  133.             int st = g * groupSize;
  134.             int nd = st + groupSize;
  135.             nd = min( nd, n );
  136.             recursiveMark(st, nd, color + 1, GRAPH);
  137.         }
  138.     }
  139. }
  140.  
  141. int main()
  142. {
  143.     ios::sync_with_stdio( false );
  144.     cin.tie(NULL);
  145.     cin >> n >> m;
  146.     edgeColors.assign(m, -1);
  147.     graph g(n);
  148.     secondGraph.resize(n);
  149.     for(int i = 0; i < m; ++i) {
  150.         int a, b;
  151.         cin >> a >> b;
  152.         --a; --b;
  153.         g.arc(a, b);
  154.         edges.emplace_back(a, b);
  155.         secondGraph[a].push_back(i);
  156.     }
  157.     g.compfortcon();
  158.     recursiveMark(0, n, 0, g);
  159.     for(const int& c : edgeColors) {
  160.         if( c == 0 ) cout << "R";
  161.         else if( c == 1) cout << "G";
  162.         else cout << "B";
  163.         cout << endl;
  164.     }
  165.     return 0;
  166. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top