Submission #1259225

#TimeUsernameProblemLanguageResultExecution timeMemory
1259225danghuyOne-Way Streets (CEOI17_oneway)C++20
100 / 100
103 ms30076 KiB
#include <bits/stdc++.h> using namespace std; #define yes cout<<"YES"<<'\n' #define no cout<<"NO"<<'\n' #define si size() #define fi first #define se second #define ll int #define sr sort #define pb push_back const ll MAXN=1e5+5,MOD=1e6,LG=19; ll n,m,j,k,p,i,f,dem,ans,t,l,r=1,timedfs; ll id[MAXN],num[MAXN],low[MAXN],mark[MAXN],a[MAXN],b[MAXN],up[MAXN][20],h[MAXN],par[MAXN],bripar[MAXN]; ll addUp[MAXN],addDown[MAXN]; vector<pair<ll,ll>> adj[MAXN],adj1[MAXN]; void dfs(ll u,ll pe){ num[u]=low[u]=++timedfs; for(auto e:adj[u]){ ll v=e.fi, idEdge=e.se; if(idEdge==pe) continue; if(!num[v]){ dfs(v,idEdge); low[u]=min(low[u],low[v]); }else low[u]=min(low[u],num[v]); } } void dfs_comp(ll u,ll comp){ stack<ll> st; st.push(u); id[u]=comp; while(!st.empty()){ ll x=st.top(); st.pop(); for(auto e:adj[x]){ ll v=e.fi; if(id[v]) continue; bool isBridge=0; if(num[x]<num[v]&&low[v]>num[x]) isBridge=1; if(num[v]<num[x]&&low[x]>num[v]) isBridge=1; if(isBridge) continue; id[v]=comp; st.push(v); } } } void dfs1(ll st,ll pre){ for(auto x:adj1[st]){ if(x.fi==pre) continue; h[x.fi]=h[st]+1; up[x.fi][0]=st; par[x.fi]=st; bripar[x.fi]=x.se; for(ll j=1;j<=LG;j++) up[x.fi][j]=up[ up[x.fi][j-1] ][j-1]; dfs1(x.fi,st); } } ll lca(ll u,ll v){ if(h[u]<h[v]) swap(u,v); ll cnt=h[u]-h[v]; for(ll j=0;j<=LG;j++) if((cnt>>j)&1) u=up[u][j]; if(u==v) return u; for(ll j=LG;j>=0;j--) if(up[u][j]!=up[v][j]) u=up[u][j],v=up[v][j]; return up[u][0]; } void go(int u,int p){ for(auto e:adj1[u]){ int v=e.fi,idEdge=e.se; if(v==p) continue; go(v,u); addUp[u]+=addUp[v]; addDown[u]+=addDown[v]; int f=(h[ id[a[idEdge]] ]<h[ id[b[idEdge]] ]?0:1); if(addUp[v]>0 && addDown[v]==0) mark[idEdge]=!f; else if(addDown[v]>0 && addUp[v]==0) mark[idEdge]=f; else mark[idEdge]=2; } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(0); cin>>n>>m; for(i=1;i<=m;i++){ ll u,v; cin>>u>>v; a[i]=u; b[i]=v; adj[u].pb({v,i}); adj[v].pb({u,i}); } for(i=1;i<=n;i++) if(!num[i]) dfs(i,0); ll comp=0; for(i=1;i<=n;i++) if(!id[i]) dfs_comp(i,++comp); for(i=1;i<=m;i++){ if(id[a[i]]==id[b[i]]) mark[i]=2; else{ bool isBridge=0; if(num[a[i]]<num[b[i]]&&low[b[i]]>num[a[i]]) isBridge=1; if(num[b[i]]<num[a[i]]&&low[a[i]]>num[b[i]]) isBridge=1; if(isBridge){ adj1[id[a[i]]].pb({id[b[i]],i}); adj1[id[b[i]]].pb({id[a[i]],i}); }else mark[i]=2; } } for(i=1;i<=comp;i++){ h[i]=0; par[i]=0; bripar[i]=0; addUp[i]=addDown[i]=0; for(j=0;j<=LG;j++) up[i][j]=0; } for(i=1;i<=comp;i++){ if(up[i][0]==0){ up[i][0]=i; dfs1(i,i); } } cin>>k; for(i=1;i<=k;i++){ ll u,v; cin>>u>>v; u=id[u]; v=id[v]; if(u==v) continue; ll w=lca(u,v); addUp[u]++; addUp[w]--; addDown[v]++; addDown[w]--; } for(i=1;i<=comp;i++) if(par[i]==0) go(i,0); for(i=1;i<=m;i++){ if(mark[i]==0) cout<<'R'; else if(mark[i]==1) cout<<'L'; else cout<<'B'; } cout<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...