Submission #878707

#TimeUsernameProblemLanguageResultExecution timeMemory
878707Ghulam_JunaidOne-Way Streets (CEOI17_oneway)C++17
0 / 100
1 ms2652 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[u]){ // (v, u) is a bridge // 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'; break; } if (!A and B){ // v to u if (edges[id].first == v) s[id] = 'R'; else s[id] = 'L'; break; } } } } else{ if (h[u] >= h[v]) continue; // u is an ancestor. 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; g[u].push_back({i, v}); g[v].push_back({i, u}); edges.push_back({u, v}); s += 'B'; } cin >> p; for (int i=0; i<p; i++){ int u, v; cin >> u >> v; important.push_back({u, v}); } dfs(1); cout << s << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...