Submission #878734

#TimeUsernameProblemLanguageResultExecution timeMemory
878734Ghulam_JunaidOne-Way Streets (CEOI17_oneway)C++17
0 / 100
1 ms2648 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, m, p, h[N], mnh[N], st[N], ft[N], tme; bool vis[N]; vector<pair<int, int>> g[N], edges, important; string s; bool in_sub(int u, int v){ return (st[v] <= st[u] && st[u] < ft[v]); } void dfs(int v, int prev = -1){ vis[v] = 1; mnh[v] = h[v]; st[v] = tme; tme++; // cout << "Running dfs on " << v << endl; for (auto [id, u] : g[v]){ if (id == prev) continue; if (!vis[u]){ h[u] = h[v] + 1; dfs(u, id); mnh[v] = min(mnh[v], mnh[u]); if (mnh[u] > h[v]){ // (v, u) is a bridge cout << u << " " << v << endl; // cout << v << " -- " << u << " is a bridge." << endl; for (auto [x, y] : important){ bool A = in_sub(x, u); bool B = in_sub(y, u); // cout << x << " " << y << " " << u << " " << A << " " << B << endl; if (A and !B){ // u to v if (edges[id].first == u) s[id] = 'R'; else s[id] = 'L'; } if (!A and B){ // v to u if (edges[id].first == v) s[id] = 'R'; else s[id] = 'L'; } } } else s[id] = 'B'; } else mnh[v] = min(mnh[v], h[u]); } ft[v] = tme; } int main(){ cin >> n >> m; for (int i=0; i<m; i++){ int u, v; cin >> u >> v; s += 'B'; edges.push_back({u, v}); if (u == v) continue; g[u].push_back({i, v}); g[v].push_back({i, u}); } for (int i=1; i<=n; i++) h[i] = mnh[i] = n + 100; cin >> p; for (int i=0; i<p; i++){ int u, v; cin >> u >> v; if (u == v) continue; important.push_back({u, v}); } for (int v = 1; v <= n; v++) if (!vis[v]) dfs(v); cout << s << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...