Submission #1259555

#TimeUsernameProblemLanguageResultExecution timeMemory
1259555danghuyOne-Way Streets (CEOI17_oneway)C++20
30 / 100
3095 ms43688 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,id[MAXN],num[MAXN]; ll low[MAXN],mark[MAXN],a[MAXN],b[MAXN],up[MAXN][20]; ll goup[MAXN],godown[MAXN],congoup[MAXN],congodown[MAXN],cntup[MAXN],cntdown[MAXN]; ll h[MAXN],par[MAXN],bripar[MAXN]; string s,s1; stack<ll> scc; vector<pair<ll,ll>> adj[MAXN],adj1[MAXN]; vector<ll> child[MAXN]; map<pair<ll,ll>,ll> ma; void dfs(ll st,ll prebri){ num[st]=low[st]=++timedfs; scc.push(st); ll f=0; for(auto x:adj[st]){ if(x.se==prebri) continue; if(!num[x.fi]){ dfs(x.fi,x.se); low[st]=min(low[st],low[x.fi]); } else { low[st]=min(low[st],num[x.fi]); } } if(low[st]==num[st]){ while(true){ ll v=scc.top();scc.pop();; id[v]=id[st]; if(v==st) break; } } } 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; child[st].pb(x.fi); for(ll j=1;j<=LG;j++){ if(up[x.fi][j-1]) up[x.fi][j]=up[up[x.fi][j-1]][j-1]; else break; } dfs1(x.fi,st); } } ll lca(ll u,ll v){ if(h[u]!=h[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 gou(ll st,ll en){ ll cnt1=0,cnt2=0; while(st!=en){ cnt1+=goup[st]; cnt2+=godown[st]; goup[st]=godown[st]=0; cntup[bripar[st]]+=cnt1; cntdown[bripar[st]]+=cnt2; st=par[st]; } } void godo(ll st,ll pre){ for(ll x:child[st]) godo(x,pre); if(child[st].size()==0) gou(st,pre); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(0); // ifstream cin("baitapin.txt"); // ofstream cout("baitapout.txt"); // freopen("oneway.INP","r",stdin); // freopen("oneway.OUT","w",stdout); cin>>n>>m; ll st; 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}); ma[{min(u,v),max(u,v)}]++; } for(i=1;i<=n;i++){ id[i]=i; } for(i=1;i<=n;i++) if(!num[i]) dfs(i,0); unordered_set<ll> s; for(i=1;i<=m;i++){ if(id[a[i]]==id[b[i]]||ma[{min(a[i],b[i]),max(a[i],b[i])}]>1) mark[i]=2; if(mark[i]!=2&&id[a[i]]!=id[b[i]]){ adj1[id[a[i]]].pb({id[b[i]],i}); adj1[id[b[i]]].pb({id[a[i]],i}); s.insert(id[a[i]]); s.insert(id[b[i]]); } } vector<ll> c; for(ll x:s){ if(h[x]) continue; c.pb(x); dfs1(x,x); } cin>>k; for(i=1;i<=k;i++){ ll u,v; cin>>u>>v; u=id[u],v=id[v]; ll k=lca(u,v); if(k==0) continue; goup[k]--; godown[k]--; goup[u]++; godown[v]++; } for(ll x:c){ godo(x,x); } for(i=1;i<=m;i++){ if(!mark[i]){ ll f=(h[id[a[i]]]<h[id[b[i]]]?0:1); if(cntup[i]) mark[i]=!f; else if(cntdown[i]) mark[i]=f; else mark[i]=2; } } for(i=1;i<=m;i++){ if(mark[i]==0) cout<<'R'; else if(mark[i]==1) cout<<'L'; else cout<<'B'; } } /* 7 8 1 5 4 2 5 7 2 3 7 1 2 3 1 4 4 3 1 1 4 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...