Submission #115058

#TimeUsernameProblemLanguageResultExecution timeMemory
115058minhtung0404One-Way Streets (CEOI17_oneway)C++17
30 / 100
3046 ms18200 KiB
//https://csacademy.com/contest/ceoi-2017-day-1/task/one-way-streets/statement/ #include<bits/stdc++.h> const int N = 1e5 + 5; using namespace std; struct edge{ int u, v, id; edge(int u, int v, int id) : u(u), v(v), id(id) {} edge() {} }; vector <edge> mv; typedef pair <int, int> ii; vector <ii> G[N], G2[N]; int n, m, q, pset[N]; int num[N], low[N], cnt, d[N], ans[N]; bool visited[N]; ii p[N]; int Find(int i) {return ((pset[i] == i) ? i : pset[i] = Find(pset[i]));} void dsu(int u, int v){ u = Find(u); v = Find(v); if (u == v) return; pset[v] = u; } void dfs(int u, int id){ num[u] = low[u] = ++cnt; for (auto p : G[u]){ int v = p.first; if (id == abs(p.second)) continue; if (num[v]) { low[u] = min(low[u], num[v]); dsu(u, v); } else { dfs(v, abs(p.second)); low[u] = min(low[u], low[v]); if (low[v] <= num[u]) dsu(u, v); else{ mv.push_back(edge(u, v, p.second)); } } } } void redfs(int u){ for(auto x : G2[u]){ if (x == p[u]) continue; int v = x.first; p[v].first = u; p[v].second = -x.second; d[v] = d[u] + 1; redfs(v); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) pset[i] = i; for (int i = 1; i <= m; i++){ int u, v; cin >> u >> v; G[u].push_back(ii(v, i)); G[v].push_back(ii(u, -i)); } for (int i = 1; i <= n; i++) if (!num[i]) dfs(i, 0); for (auto ed : mv){ ed.u = Find(ed.u); ed.v = Find(ed.v); G2[ed.u].push_back(ii(ed.v, ed.id)); G2[ed.v].push_back(ii(ed.u, -ed.id)); } for (int i = 1; i <= n; i++) if (pset[i] == i && !visited[i]) redfs(i); cin >> q; cnt = 0; while (q--){ int u, v; cin >> u >> v; u = Find(u); v = Find(v); while (u != v){ if (d[u] > d[v]) { dsu(p[u].first, u); ans[abs(p[u].second)] = ((p[u].second > 0) ? 1 : 2); u = Find(p[u].first); cnt++; } else{ dsu(p[v].first, v); ans[abs(p[v].second)] = ((p[v].second > 0) ? 2 : 1); v = Find(p[v].first); cnt++; } if (cnt > n) assert(0); } } for (int i = 1; i <= m; i++){ if (ans[i] == 0) cout << "B"; if (ans[i] == 1) cout << "R"; if (ans[i] == 2) cout << "L"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...