Submission #938750

#TimeUsernameProblemLanguageResultExecution timeMemory
938750AiperiiiOne-Way Streets (CEOI17_oneway)C++14
0 / 100
2 ms10528 KiB
#include <bits/stdc++.h> #define int long long #define ff first #define ss second #define pb push_back #define all(x) x.begin(),x.end() using namespace std; const int N=1e5+5; vector <int> g_brg[N]; vector <pair <int,int> > g_gr[N]; int vis_brg[N],low[N],tin[N],gr[N],To[N],from[N],vis_gr[N]; char ans[N]; map <pair <int,int> ,int> brg; int tt=0,cnt=0; void dfs_brg(int v,int p){ vis_brg[v]=1; tt++; tin[v]=tt;low[v]=tt; for(auto to : g_brg[v]){ if(to!=p){ if(vis_brg[to])low[v]=min(low[v],tin[to]); else{ dfs_brg(to,v); low[v]=min(low[v],low[to]); if(low[to]>tin[v]){ brg[{v,to}]++; brg[{to,v}]++; } } } } } void groups(int v,int p){ gr[v]=cnt; for(auto to : g_brg[v]){ if(to!=p && !gr[to]){ if(brg[{v,to}]!=1)groups(to,v); } } } void dfs(int v,int p){ vis_gr[v]=1; for(auto to : g_gr[v]){ if(to.ff!=p)dfs(to.ff,v); } from[p]+=from[v]; To[p]+=To[v]; for(auto to : g_gr[v]){ if(to.ff!=p){ if(from[to.ff]<To[to.ff]){ if(to.ss<0)ans[abs(to.ss)]='L'; else ans[to.ss]='R'; } else if(from[to.ff]>from[to.ss]){ if(to.ss<0)ans[abs(to.ss)]='R'; else ans[to.ss]='L'; } } } } signed main(){ ios_base::sync_with_stdio(); cin.tie(0);cout.tie(0); int n,m; cin>>n>>m; vector <int> a(m),b(m); for(int i=0;i<m;i++){ cin>>a[i]>>b[i]; g_brg[a[i]].pb(b[i]); g_brg[b[i]].pb(a[i]); } for(int i=1;i<=n;i++){ if(!vis_brg[i])dfs_brg(i,0); } for(int i=1;i<=n;i++){ if(!gr[i]){ cnt++; groups(i,0); } } for(int i=0;i<m;i++){ if(gr[a[i]]!=gr[b[i]]){ g_gr[gr[a[i]]].pb({gr[b[i]],i}); g_gr[gr[b[i]]].pb({gr[a[i]],-i}); } } int q;cin>>q; while(q--){ int s,t; cin>>s>>t; from[gr[s]]++; To[gr[t]]++; } for(int i=0;i<m;i++)ans[i]='B'; for(int i=1;i<=cnt;i++){ if(!vis_gr[i]){ dfs(i,0); } } for(int i=0;i<m;i++)cout<<ans[i]; } /* 5 6 1 2 1 2 4 3 2 3 1 3 5 1 2 4 5 1 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...