Submission #881871

#TimeUsernameProblemLanguageResultExecution timeMemory
881871SharkyOne-Way Streets (CEOI17_oneway)C++17
0 / 100
2 ms10332 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100010; const int lg = 18; #define fi first #define se second vector<pair<int, int>> adj[N]; pair<int, int> edges[N]; set<int> b; vector<char> ans(N, 'B'); int n, m, pairs, low[N], st[N], timer = 0, k = 0, bcc[N], road_id = 0, lift[N][lg], dep[N], pa[N]; pair<int, int> up[N], down[N]; struct edge { int v, id; char dir; }; vector<edge> g[N]; void dfs(int u, int p) { low[u] = st[u] = ++timer; for (auto& [v, id] : adj[u]) { if (!st[v]) { dfs(v, u); low[u] = min(low[u], low[v]); if (low[v] > st[u]) b.insert(id); } else if (v != p) { low[u] = min(low[u], st[v]); } } } void Dfs(int u) { bcc[u] = k; for (auto& [v, id] : adj[u]) { if (b.count(id)) continue; if (!bcc[v]) Dfs(v); } } void pre(int u) { for (int i = 1; i < lg; i++) lift[u][i] = lift[lift[u][i - 1]][i - 1]; for (auto& [v, id, dir] : g[u]) { if (lift[u][0] != v) { dep[v] = dep[u] + 1; pa[v] = u; lift[v][0] = u; pre(v); } } } int jump(int sta, int dist) { for (int i = lg - 1; i >= 0; i--) if (dist & (1 << i)) sta = lift[sta][i]; return sta; } int get_lca(int u, int v) { if (dep[u] > dep[v]) swap(u, v); v = jump(v, dep[v] - dep[u]); if (u == v) return u; for (int i = lg - 1; i >= 0; i--) { int ut = lift[u][i], vt = lift[v][i]; if (ut != vt) u = ut, v = vt; } return lift[u][0]; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0, u, v; i < m; i++) { cin >> u >> v; road_id++; adj[u].push_back({v, road_id}); adj[v].push_back({u, road_id}); edges[road_id] = {u, v}; } dfs(1, 0); for (int i = 1; i <= n; i++) { if (!bcc[i]) { k++; Dfs(i); } } for (int i = 1; i <= m; i++) { int u = bcc[edges[i].fi], v = bcc[edges[i].se]; if (u == v) continue; g[u].push_back((edge) {v, i, 'R'}); g[v].push_back((edge) {u, i, 'L'}); } lift[1][0] = 1; pre(1); for (int i = 1; i <= m; i++) { int u = bcc[edges[i].fi], v = bcc[edges[i].se]; if (u == v) continue; if (dep[u] > dep[v]) up[u] = {i, 'R'}; else up[v] = {i, 'L'}; } cin >> pairs; while (pairs--) { int u, v; cin >> u >> v; u = bcc[u], v = bcc[v]; int lca = get_lca(u, v); while (u != lca) ans[up[u].first] = up[u].second, u = pa[u]; while (v != lca) ans[up[v].first] = (up[v].second == 'R' ? 'L' : 'R'), v = pa[v]; } for (int i = 1; i <= m; i++) cout << ans[i]; cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...