Submission #1005154

#TimeUsernameProblemLanguageResultExecution timeMemory
1005154SulAOne-Way Streets (CEOI17_oneway)C++17
0 / 100
3042 ms12632 KiB
#include <bits/stdc++.h> using namespace std; struct DSU { vector<int> par, size; DSU(int n = 0) { par.resize(n+1, 0); size.resize(n+1, 0); for (int i = 1; i <= n; i++) { par[i] = i; } } int find(int v) { return par[v] == v ? v : par[v] = find(par[v]); } void merge(int a, int b) { a = find(a), b = find(b); if (a != b) { if (size[a] < size[b]) swap(a,b); par[b] = a; size[a] += size[b]; } } }; const int MAXN = 100000; vector<int> adj[MAXN+1]; vector<int> comp[MAXN+1]; vector<pair<int,int>> bridges, graph; map<pair<int,int>,int> ind; map<pair<int,int>,pair<int,int>> compToOriginal; DSU d; int dep[MAXN + 1], low[MAXN + 1], par[17][MAXN + 1], lay[MAXN + 1]; void dfs1(int v, int p) { dep[v] = low[v] = dep[p] + 1; for (int u : adj[v]) { if (u == p) continue; if (dep[u] == 0) { dfs1(u, v); low[v] = min(low[v], low[u]); } else { low[v] = min(low[v], dep[u]); d.merge(v, u); } } if (v == 1) return; if (low[v] == dep[v]) { if (binary_search(graph.begin(), graph.end(), make_pair(p,v))) { bridges.push_back({p,v}); } else { bridges.push_back({v,p}); } } else { d.merge(p, v); } } void dfs2(int v, int p) { par[0][v] = p; lay[v] = lay[p] + 1; for (int k = 1; k < 17; k++) { par[k][v] = par[k-1][par[k-1][v]]; } for (auto u : comp[v]) if (u != p) { dfs2(u, v); } } int lca(int a, int b) { if (lay[a] > lay[b]) swap(a, b); int dif = lay[b] - lay[a]; for (int i = 17; i >= 0; i--) { if (dif & (1 << i)) { b = par[i][b]; } } if (a == b) return a; for (int i = 17; i >= 0; i--) { if (par[i][a] != par[i][b]) { a = par[i][a]; b = par[i][b]; } } return par[0][a]; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n,m; cin >> n >> m; char ans[m]; fill(ans, ans + m, 'B'); d = DSU(n); for (int i = 0; i < m; i++) { int a,b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); graph.push_back({a,b}); ind[{a,b}] = i; } sort(graph.begin(), graph.end()); dfs1(1, 0); for (auto [a,b] : bridges) { int compa = d.find(a), compb = d.find(b); comp[compa].push_back(compb); comp[compb].push_back(compa); compToOriginal[{min(compa, compb), max(compa, compb)}] = {a,b}; } int root; for (int v = 1; v <= n; v++) if (v == d.find(v)) { root = v; dfs2(root, root); break; } int q; cin >> q; while (q--) { int a,b; cin >> a >> b; a = d.find(a), b = d.find(b); if (a == b) continue; int L = lca(a,b); while (a != L) { int p = par[0][a]; auto [oldv, oldu] = compToOriginal[{min(a,p), max(a,p)}]; if (ind.find({oldv, oldu}) != ind.end()) { int index = ind[{oldv, oldu}]; ans[index] = 'R'; } else { int index = ind[{oldu, oldv}]; ans[index] = 'L'; } a = p; } while (b != L) { int p = par[0][b]; auto [oldu, oldv] = compToOriginal[{min(b,p), max(b,p)}]; if (ind.find({oldv, oldu}) != ind.end()) { int index = ind[{oldv, oldu}]; ans[index] = 'R'; } else { int index = ind[{oldu, oldv}]; ans[index] = 'L'; } b = p; } } for (char c : ans) cout << c; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...