Submission #1226871

#TimeUsernameProblemLanguageResultExecution timeMemory
1226871lukasuliashviliOne-Way Streets (CEOI17_oneway)C++20
0 / 100
5 ms11584 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; vector<pair<int, int>> g[N]; int tin[N], low[N], timer; bool isBridge[N]; int comp[N], compCnt; vector<int> tree[N]; int par[N][17], depth[N]; map<pair<int, int>, int> bridgeToIndex; struct Edge { int u, v; }; Edge edges[N]; int edgeDir[N]; void dfsBridge(int v, int p = -1, int pIdx = -1) { tin[v] = low[v] = ++timer; for (auto [to, idx] : g[v]) { if (to == p && idx == pIdx) continue; if (tin[to]) { low[v] = min(low[v], tin[to]); } else { dfsBridge(to, v, idx); low[v] = min(low[v], low[to]); if (low[to] > tin[v]) { isBridge[idx] = true; } } } } void dfsComponent(int u, int c) { comp[u] = c; for (auto [v, idx] : g[u]) { if (comp[v] == -1 && !isBridge[idx]) { dfsComponent(v, c); } } } void dfsLCA(int u, int p) { par[u][0] = p; for (int i = 1; i < 17; ++i) { if (par[u][i - 1] != -1) par[u][i] = par[par[u][i - 1]][i - 1]; } for (int v : tree[u]) { if (v != p) { depth[v] = depth[u] + 1; dfsLCA(v, u); } } } int lca(int u, int v) { if (depth[u] < depth[v]) swap(u, v); for (int i = 16; i >= 0; --i) if (par[u][i] != -1 && depth[par[u][i]] >= depth[v]) u = par[u][i]; if (u == v) return u; for (int i = 16; i >= 0; --i) if (par[u][i] != -1 && par[u][i] != par[v][i]) u = par[u][i], v = par[v][i]; return par[u][0]; } void mark(int u, int v, int up) { while (u != v) { int p = par[u][0]; int a = u, b = p; if (a > b) swap(a, b); int idx = bridgeToIndex[{a, b}]; if (up) edgeDir[idx] |= 1; else edgeDir[idx] |= 2; u = p; } } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; --u, --v; g[u].emplace_back(v, i); g[v].emplace_back(u, i); edges[i] = {u, v}; } dfsBridge(0); fill(comp, comp + n, -1); compCnt = 0; for (int i = 0; i < n; ++i) { if (comp[i] == -1) dfsComponent(i, compCnt++); } int id = 0; for (int i = 0; i < m; ++i) { if (isBridge[i]) { int a = comp[edges[i].u]; int b = comp[edges[i].v]; tree[a].push_back(b); tree[b].push_back(a); int u = min(a, b), v = max(a, b); bridgeToIndex[{u, v}] = id++; } } memset(par, -1, sizeof par); dfsLCA(0, -1); int p; cin >> p; while (p--) { int u, v; cin >> u >> v; u = comp[--u]; v = comp[--v]; int w = lca(u, v); mark(u, w, 1); mark(v, w, 0); } string res; for (int i = 0; i < m; ++i) { if (!isBridge[i]) { res += 'B'; } else { int a = comp[edges[i].u]; int b = comp[edges[i].v]; int u = min(a, b), v = max(a, b); int idx = bridgeToIndex[{u, v}]; int cu = comp[edges[i].u], cv = comp[edges[i].v]; if (edgeDir[idx] == 1) { if (cu == a && cv == b) res += 'R'; else res += 'L'; } else if (edgeDir[idx] == 2) { if (cu == a && cv == b) res += 'L'; else res += 'R'; } else { res += 'B'; } } } cout << res << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...