Submission #926388

#TimeUsernameProblemLanguageResultExecution timeMemory
926388RegulusOne-Way Streets (CEOI17_oneway)C++17
100 / 100
124 ms38908 KiB
#include <bits/stdc++.h> #define IO ios::sync_with_stdio(false);cin.tie(0); #define debug(x) cerr << #x << " = " << (x) << ' ' #define bug(x) cerr << (x) << ' ' #define endl cerr << '\n' #define all(v) (v).begin(), (v).end() #define SZ(v) (ll)(v).size() #define lowbit(x) (x)&-(x) #define pb emplace_back #define F first #define S second using namespace std; using ll = long long; using pll = pair<ll, ll>; const int N = 1e5+5; const int LogN = 17; int dfn[N], low[N], timer, tag[LogN+5][N], tin[N], tout[N], anc[LogN+5][N]; pll e[N]; bool cut[N]; vector<pll> g[N]; vector<int> tr[N]; inline void tarjan(int x, int pid) { dfn[x] = low[x] = ++timer; for (auto e : g[x]) { int v = e.F, id = e.S; if (id == pid) continue; if (!dfn[v]) { tarjan(v, id); tr[x].pb(v), tr[v].pb(x); low[x] = min(low[x], low[v]); } else { low[x] = min(low[x], dfn[v]); } if (low[v] > dfn[x]) cut[id] = 1; } } inline bool is_anc(int x, int y) { return tin[x] < tin[y] && tout[y] < tout[x]; } inline void dfs(int x, int pre) { tin[x] = ++timer, anc[0][x] = pre; for (int v : tr[x]) if (v != pre) dfs(v, x); tout[x] = ++timer; } inline int get_lca(int x, int y) { if (is_anc(x, y)) return x; if (is_anc(y, x)) return y; for (int i=LogN; i >= 0; --i) if (anc[i][x] && !is_anc(anc[i][x], y)) x = anc[i][x]; return anc[0][x]; } inline void update(int x, int y, int c) { for (int i=LogN; i >= 0; --i) { if (anc[i][x] && !is_anc(anc[i][x], y)) tag[i][x] |= c, x = anc[i][x]; } } int main(void) { IO int n, i, m, Q; cin >> n >> m; for (i=1; i <= m; ++i) { int x, y; cin >> x >> y, e[i] = {x, y}; g[x].pb(y, i), g[y].pb(x, i); } for (i=1; i <= n; ++i) { if (!dfn[i]) { tarjan(i, 0); dfs(i, 0); } } for (i=1; i <= LogN; ++i) for (int j=1; j <= n; ++j) anc[i][j] = anc[i-1][anc[i-1][j]]; cin >> Q; do { int x, y; cin >> x >> y; if (x == y) continue; int tmp = get_lca(x, y); update(x, tmp, 1), update(y, tmp, 2); } while (--Q); for (i=LogN; i > 0; --i) { for (int j=1; j <= n; ++j) { tag[i-1][j] |= tag[i][j]; tag[i-1][anc[i-1][j]] |= tag[i][j]; } } for (i=1; i <= m; ++i) { if (!cut[i]) cout << "B"; else { int x = e[i].F, y = e[i].S; if (tin[x] < tin[y]) swap(x, y); if (tag[0][x] == 3) assert(0); if (tag[0][x] == 1) { if (x == e[i].F) cout << "R"; else cout << "L"; } else if (tag[0][x] == 2) { if (x == e[i].F) cout << "L"; else cout << "R"; } else { cout << "B"; } } } cout << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...