• API
• FAQ
• Tools
• Archive
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
44.   int inv(int a) { return a ^ 0x1; }
45.   graph(int n = 0) {
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);
53.     dest.pb(i);
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() {
96.     ord.clear();
97.     fu(u, sz(adj)) if (depth[u] == -1) {
98.         depth[u] = 0;
99.         dfs_topsort(u);
100.     }
101.
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.

Top