Submission #1265139

#TimeUsernameProblemLanguageResultExecution timeMemory
1265139escobrandOne-Way Streets (CEOI17_oneway)C++20
100 / 100
53 ms19012 KiB
// 2-Edge Connected Component /* documents https://usaco.guide/adv/BCC-2CC https://codeforces.com/blog/entry/83980 */ #include <bits/stdc++.h> using namespace std; #define all(v) v.begin(),v.end() #define pb push_back #define ll long long #define ld long double #define fi first #define se second #define mk make_pair typedef pair<int,int> pii; const int maxn = 1e5 + 10; vector<pii> adj[maxn]; char ans[maxn]; //Code 2-Edge Connected Component stack<int> st; int com[maxn],low[maxn],tim[maxn]; int t,com_cnt; vector<pii> com_adj[maxn]; // DFS to find 2-edge connected component for each node void dfs(int i,int pa) // O( n ) { low[i] = tim[i] = ++t; // Set discovery and low time st.push(i); // Add node to the stack bool through = 0; for(pii k : adj[i]) { // Skip edge to parent (once (!) ) if(k.fi == pa && !through) { through = 1; continue; } if(tim[k.fi])low[i] = min(low[i],tim[k.fi]); else { dfs(k.fi,i); low[i] = min(low[i],low[k.fi]); } } // If node is root of a component if(low[i] == tim[i]) { ++com_cnt; // Pop nodes from stack to form component while(st.top() != i) { com[st.top()] = com_cnt; st.pop(); } com[st.top()] = com_cnt; st.pop(); } } // Build the compressed component graph void compress_graph(int n) // O( n ) { for(int i = 1;i<=n;i++) { for(pii k : adj[i]) { // Add edge between different components if(com[i] != com[k.fi]) com_adj[com[i]].pb( mk(com[k.fi],k.se) ); } } } //End Code 2-Edge Connected Component bool c[maxn]; int dp[maxn]; void cal(int i,int pa) { c[i] = 1; for(pii k : com_adj[i]) { if(k.fi == pa)continue; cal(k.fi,i); dp[i] += dp[k.fi]; dp[k.fi] *= k.se / abs(k.se); // change sign of edge if(dp[k.fi] < 0)ans[abs(k.se)] = 'R'; if(dp[k.fi] > 0)ans[abs(k.se)] = 'L'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); // https://oj.uz/problem/view/CEOI17_oneway int n,m; cin>>n>>m; for(int i = 1;i<=m;i++) { int u,v; cin>>u>>v; adj[u].pb(mk(v,i)); adj[v].pb(mk(u,-i)); // edges made of pairs are for solving the problem, dont mind it ans[i] = 'B'; } // Find all 2-edge connected components for(int i = 1;i<=n;i++) { if(!tim[i]) dfs(i,0); } // Compress the graph using components compress_graph(n); int q; cin>>q; while(q--) { int u,v; cin>>u>>v; u = com[u]; v = com[v]; dp[u]++; dp[v]--; } for(int i = 1;i<=com_cnt;i++) { if(!c[i])cal(i,0); } for(int i = 1;i<=m;i++)cout<<ans[i]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...