Submission #1257851

#TimeUsernameProblemLanguageResultExecution timeMemory
1257851MinhKienOne-Way Streets (CEOI17_oneway)C++20
100 / 100
133 ms25144 KiB
#include <iostream> #include <vector> #include <stack> #include <set> using namespace std; #define ii pair <int, int> #define fi first #define se second const int N = 1e5 + 10; int n, m, x, y; vector <ii> v[N]; vector <int> g[N]; ii e[N]; int num[N], low[N], scc[N]; int cnt, tim; stack <int> st; void DFS(int s, int p = -1) { num[s] = low[s] = ++tim; st.push(s); for (ii z: v[s]) { if (z.se == p) continue; if (num[z.fi]) { low[s] = min(low[s], num[z.fi]); } else { DFS(z.fi, z.se); low[s] = min(low[s], low[z.fi]); } } if (num[s] == low[s]) { scc[s] = ++cnt; while (st.top() != s) { scc[st.top()] = cnt; st.pop(); } st.pop(); } } int dp[N]; bool vis[N]; set <ii> ms; void DFS2(int s, int p = -1) { vis[s] = true; for (int z: g[s]) { if (z == p) continue; DFS2(z, s); dp[s] += dp[z]; } if (dp[s] > 0) { ms.insert(ii(s, p)); } else { if (dp[s] < 0) { ms.insert(ii(p, s)); } } } int main() { // freopen("oneway.inp", "r", stdin); // freopen("oneway.out", "w", stdout); cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= m; ++i) { cin >> x >> y; e[i] = ii(x, y); v[x].push_back(ii(y, i)); v[y].push_back(ii(x, i)); } for (int i = 1; i <= n; ++i) { if (!num[i]) DFS(i); } for (int i = 1; i <= n; ++i) { for (ii z: v[i]) { if (scc[i] == scc[z.fi]) continue; g[scc[i]].push_back(scc[z.fi]); } } int q; cin >> q; while (q--) { cin >> x >> y; if (scc[x] == scc[y]) continue; ++dp[scc[x]]; --dp[scc[y]]; } for (int i = 1; i <= cnt; ++i) { if (!vis[i]) DFS2(i); } for (int i = 1; i <= m; ++i) { x = e[i].fi, y = e[i].se; if (scc[x] == scc[y]) { cout << 'B'; continue; } if (ms.find(ii(scc[x], scc[y])) != ms.end()) cout << 'R'; else if (ms.find(ii(scc[y], scc[x])) != ms.end()) cout << 'L'; else cout << 'B'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...