Submission #872837

#TimeUsernameProblemLanguageResultExecution timeMemory
872837MisterReaperOne-Way Streets (CEOI17_oneway)C++17
0 / 100
0 ms348 KiB
//author: Ahmet Alp Orakci #include <bits/stdc++.h> using namespace std; using i64 = long long; #define ONLINE_JUDGE void solve() { int n, m; cin >> n >> m; map <pair <int, int>, int> mp; vector <pair <int, int>> adj[n +1]; vector <pair <int, int>> edges(m); for(int i = 0; i < m; i++) { cin >> edges[i].first >> edges[i].second; adj[edges[i].first].emplace_back(edges[i].second, i); adj[edges[i].second].emplace_back(edges[i].first, i); mp[{min(edges[i].first, edges[i].second), max(edges[i].first, edges[i].second)}]++; } int timer = 0; vector <int> tin(n +1, -1), low(n +1, -1), is_bridge(m); function <void(int, int)> dfs = [&](int node, int par) -> void { low[node] = tin[node] = timer++; for(auto [child, number] : adj[node]) { if(child == par) { continue; } if(tin[child] == -1) { dfs(child, node); low[node] = min(low[node], low[child]); if(low[child] > tin[node]) { //cerr << node << " " << child << " :: " << number << "\n"; is_bridge[number] = true; } } else { low[node] = min(low[node], tin[child]); } } }; for(int i = 1; i <= n; i++) { if(tin[i] == -1) { dfs(i, -1); } } string res(m, 'B'); for(int i = 0; i < m; i++) { if(mp[{min(edges[i].first, edges[i].second), max(edges[i].first, edges[i].second)}] > 1) { //cerr << edges[i].first << " " << edges[i].second << " :: " << i << "\n"; is_bridge[i] = false; } if(is_bridge[i]) { res[i] = 'X'; } } //cerr << res << "\n"; vector <int> compo(n +1, -1); function <void(int, int)> dfsC = [&](int node, int color) { compo[node] = color; for(auto [child, num] : adj[node]) { if(compo[child] == -1 && !is_bridge[num]) { dfsC(child, color); } } }; int col = 0; for(int i = 1; i <= n; i++) { if(compo[i] == -1) { dfsC(i, col); col++; } } /* for(int i = 1; i <= n; i++) { cerr << compo[i] << " \n"[i == n]; } */ vector <pair <int, int>> nadj[col]; for(int i = 0; i < m; i++) { if(is_bridge[i]) { int x = compo[edges[i].first], y = compo[edges[i].second]; //cerr << i << " -> " << edges[i].first << " " << edges[i].second << " :: " << compo[edges[i].first] << " " << compo[edges[i].second] << "\n"; nadj[min(x, y)].emplace_back(max(x, y), i); } } int p; cin >> p; vector <int> val(col); for(int i = 1; i <= p; i++) { int a, b; cin >> a >> b; //cerr << a << " " << b << " :: " << compo[a] << " " << compo[b] << "\n"; val[compo[a]]++; val[compo[b]]--; } vector <int> vis(col, -1); function <void(int)> DFS = [&](int node) -> void { vis[node] = 0; for(auto [child, num] : nadj[node]) { if(vis[child] == -1) DFS(child); val[node] += val[child]; vis[node] = max(vis[node], vis[child] +1); } }; for(int i = 0; i < col; i++) { if(vis[i] == -1) { DFS(i); } } for(int i = 0; i < m; i++) { if(res[i] == 'X') { int x = compo[edges[i].first], y = compo[edges[i].second]; //cerr << edges[i].first << " " << edges[i].second << " :: " << x << " " << y << " -> " << val[x] << " " << val[y] << "\n"; if(vis[x] > vis[y]) { if(val[y] > 0) res[i] = 'L'; else if(val[y] < 0) res[i] = 'R'; else res[i] = 'B'; } else if(x > y) { if(val[x] > 0) res[i] = 'R'; else if(val[x] < 0) res[i] = 'L'; else res[i] = 'B'; } else { res[i] = 'B'; } } } cout << res; return; } signed main() { #ifndef ONLINE_JUDGE freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; //cin >> t; for(int i = 1; i <= t; i++) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...