Submission #904032

#TimeUsernameProblemLanguageResultExecution timeMemory
904032Dec0DeddOne-Way Streets (CEOI17_oneway)C++14
0 / 100
6 ms20700 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int N = 1e5+10; const int K = 20; vector<int> G[N]; set<int> T[N]; int n, m, p, x[N], y[N], a[N], b[N], tin[N], tout[N], low[N], rt[N], t; pii prf[N]; int up[K][N]; bool vis[N]; map<pii, bool> brg; map<pii, int> eds; vector<int> vcs[N]; void brd(int v, int p) { vis[v]=true; tin[v]=low[v]=t++; for (auto u : G[v]) { if (u == p) continue; if (vis[u]) low[v]=min(low[v], tin[u]); else { brd(u, v); low[v]=min(low[v], low[u]); if (low[u] > tin[v]) brg[{u, v}]=brg[{v, u}]=true; } } } void gen(int v, int r) { vis[v]=true; rt[v]=r; vcs[r].push_back(v); for (auto u : G[v]) { if (vis[u]) continue; if (brg[{v, u}]) gen(u, u); else gen(u, r); } } void dfs(int v, int p) { up[0][v]=p; for (int i=1; i<K; ++i) up[i][v]=up[i-1][up[i-1][v]]; tin[v]=++t; for (auto u : T[v]) { if (u == p) continue; dfs(u, v); } tout[v]=t; } bool anc(int v, int u) { return tin[v] <= tin[u] && tout[u] <= tout[v]; } int lca(int v, int u) { if (anc(v, u)) return v; if (anc(u, v)) return u; for (int i=K-1; i>=0; --i) { if (!anc(up[i][v], u)) v=up[i][v]; } return up[0][v]; } pii mrg(pii a, pii b) { return {a.first+b.first, a.second+b.second}; } void repl(int v, int p) { for (auto u : T[v]) { if (u == p) continue; repl(u, v); prf[v]=mrg(prf[v], prf[u]); } } void solve() { cin>>n>>m; for (int i=1; i<=m; ++i) { cin>>a[i]>>b[i]; G[a[i]].push_back(b[i]); G[b[i]].push_back(a[i]); ++eds[{a[i], b[i]}]; } for (int i=1; i<=n; ++i) { if (vis[i]) continue; brd(i, i); } memset(vis, false, sizeof(vis)); for (int i=1; i<=m; ++i) { if (eds[{a[i], b[i]}] > 1 || eds[{b[i], a[i]}]) brg[{a[i], b[i]}]=false; } for (int i=1; i<=n; ++i) { if (vis[i]) continue; gen(i, i); } for (int i=1; i<=n; ++i) { if (rt[i] != i) continue; for (auto v : vcs[i]) { for (auto u : G[v]) { if (rt[u] == rt[v]) continue; T[i].insert(rt[u]); } } } memset(vis, false, sizeof(vis)); memset(tin, false, sizeof(tin)); memset(low, false, sizeof(low)); t=0; vector<int> vx; for (int i=1; i<=n; ++i) { if (rt[i] != i) continue; if (tin[i]) continue; dfs(i, i), vx.push_back(i); } cin>>p; for (int i=1; i<=p; ++i) { cin>>x[i]>>y[i]; x[i]=rt[x[i]], y[i]=rt[y[i]]; int l=lca(x[i], y[i]); ++prf[x[i]].first; ++prf[y[i]].second; --prf[l].first, --prf[l].second; } for (auto u : vx) repl(u, u); for (int i=1; i<=m; ++i) { int ra=rt[a[i]], rb=rt[b[i]]; if (ra == rb) cout<<"B"; else { if (anc(ra, rb)) { // a is anc assert(!(prf[rb].first > 0 && prf[rb].second > 0)); if (prf[rb].first > 0) { // go towards ancestor b -> a cout<<"L"; } else if (prf[rb].second > 0) { // go towards son a -> b cout<<"R"; } else cout<<"B"; } else { assert(!(prf[ra].first > 0 && prf[ra].second > 0)); if (prf[ra].first > 0) { // go towards ancestor a -> b cout<<"R"; } else if (prf[ra].second > 0) { cout<<"L"; } else cout<<"B"; } } } cout<<"\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int t=1; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...