Submission #1259550

#TimeUsernameProblemLanguageResultExecution timeMemory
1259550vuvietOne-Way Streets (CEOI17_oneway)C++20
100 / 100
128 ms45056 KiB
/** * __ __ __ __ * \ \ / / \ \ / (_) _____ * \ \ / /_ _\ \ / / _ ___|_ _| * \ \/ /| | | |\ \/ / | |/ _ \ | | * \ / | |_| | \ / | | __/ | | * \/ \__,_| \/ |_|\____||_| * * Author: ~Noah-kun~ * Created: 2025-08-17 15:22 **/ #include <bits/stdc++.h> using namespace std; #define int long long #define ____VuViet__ signed main const int N = 1e5 + 5; typedef pair<int, int> pii; int cnt = 0, id = 0, n, m, k; int num[N], low[N], comp[N], sum[N]; int res[N], inStk[N], vis[N]; set<pii> g1[N], g2[N]; stack<int> stk; void Tarjan(int u, int p) { num[u] = low[u] = ++id; inStk[u] = 1; stk.push(u); for (auto [v, id] : g1[u]) { if (id == -p) continue; if (!num[v]) { Tarjan(v, id); low[u] = min(low[u], low[v]); } else if (inStk[v]) { low[u] = min(low[u], num[v]); } } if (low[u] >= num[u]) { ++cnt; int v; do { v = stk.top(); stk.pop(); inStk[v] = 0; comp[v] = cnt; } while (v != u); } } void ReadData() { cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; g1[u].insert({v, i}); g1[v].insert({u, -i}); } } void DFS(int u, int edgeId, int way) { vis[u] = 1; for (auto [v, id] : g2[u]) { if (vis[v]) continue; int nextWay = (id > 0) ? 1 : -1; DFS(v, abs(id), nextWay); sum[u] += sum[v]; } if (sum[u] != 0 && edgeId != 0) { res[edgeId] = (sum[u] * way > 0) ? 1 : 2; } } char GetChar(int x) { if (x == 0) return 'B'; if (x == 1) return 'L'; return 'R'; } void Solve() { for (int i = 1; i <= n; i++) if (!num[i]) Tarjan(i, i); for (int u = 1; u <= n; u++) for (auto [v, id] : g1[u]) if (comp[u] != comp[v]) g2[comp[u]].insert({comp[v], id}); cin >> k; while (k--) { int u, v; cin >> u >> v; ++sum[comp[u]], --sum[comp[v]]; } for (int i = 1; i <= cnt; i++) if (!vis[i]) DFS(i, 0, 0); for (int i = 1; i <= m; i++) cout << GetChar(res[i]); } ____VuViet__() { ReadData(); Solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...