Submission #147291

#TimeUsernameProblemLanguageResultExecution timeMemory
147291MvCOne-Way Streets (CEOI17_oneway)C++11
100 / 100
234 ms30712 KiB
#pragma GCC target("avx2") #pragma GCC optimization("O3") #pragma GCC optimization("unroll-loops") #include<bits/stdc++.h> //#include "boxes.h" #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<61); const int inf=(1<<30); const int nmax=1e5+50; const int mod=1e9+7; using namespace std; int n,m,i,fin[nmax],fup[nmax],br[nmax],x,y,l,tin,ex[nmax],ey[nmax],par[nmax][20],c[nmax],k,in[nmax],out[nmax],z,up[nmax],dw[nmax]; vector<int>a[nmax]; vector<pair<int,int> >g[nmax]; bitset<nmax>viz; char rs[nmax]; void dfs(int x,int p=-1) { viz[x]=1; fin[x]=fup[x]=++tin; for(int i=0;i<a[x].size();i++) { if(a[x][i]==p)continue; int y=x^ex[a[x][i]]^ey[a[x][i]]; if(viz[y]) { fup[x]=min(fup[x],fin[y]); } else { dfs(y,a[x][i]); fup[x]=min(fup[x],fup[y]); if(fup[y]>fin[x]) { br[a[x][i]]=1; } } } } void col(int x) { viz[x]=1; c[x]=k; for(int i=0;i<a[x].size();i++) { int y=x^ex[a[x][i]]^ey[a[x][i]]; if(viz[y] || br[a[x][i]])continue; col(y); } } void con(int x) { viz[x]=1; for(int i=0;i<a[x].size();i++) { int y=x^ex[a[x][i]]^ey[a[x][i]]; if(br[a[x][i]]) { g[c[x]].pb(mkp(c[y],a[x][i])); //g[c[y]].pb(c[x]); continue; } if(viz[y])continue; con(y); } } void build(int x,int p) { viz[x]=1; par[x][0]=p; in[x]=++tin; for(int i=1;i<18;i++)par[x][i]=par[par[x][i-1]][i-1]; for(int i=0;i<g[x].size();i++) { int y=g[x][i].fr; if(y==p)continue; build(y,x); } out[x]=++tin; } int anc(int x,int y) { return in[x]<=in[y] && out[y]<=out[x]; } int lca(int x,int y) { if(anc(x,y))return x; if(anc(y,x))return y; for(int i=17;i>=0;i--)if(!anc(par[x][i],y))x=par[x][i]; return par[x][0]; } void rec(int x,int p,int ed) { viz[x]=1; for(int i=0;i<g[x].size();i++) { int y=g[x][i].fr; if(y==p)continue; rec(y,x,g[x][i].sc); up[x]+=up[y]; dw[x]+=dw[y]; } //cout<<x<<" "<<ed<<" "<<up[x]<<" "<<dw[x]<<endl; if(up[x]) { if(c[ex[ed]]==x)rs[ed]='R'; else rs[ed]='L'; } if(dw[x]) { if(c[ex[ed]]==x)rs[ed]='L'; else rs[ed]='R'; } } int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); cin>>n>>m; for(i=1;i<=m;i++) { cin>>ex[i]>>ey[i]; a[ex[i]].pb(i); a[ey[i]].pb(i); } for(i=1;i<=n;i++) { if(!viz[i]) { dfs(i); } } viz.reset(); for(i=1;i<=n;i++) { if(!viz[i]) { k++; col(i); } } viz.reset(); for(i=1;i<=n;i++) { if(!viz[i]) { con(i); } } viz.reset(); for(i=1;i<=k;i++) { if(viz[i])continue; build(i,i); } cin>>z; while(z--) { cin>>x>>y; x=c[x],y=c[y]; l=lca(x,y); up[x]++; up[l]--; dw[y]++; dw[l]--; } viz.reset(); for(i=1;i<=k;i++) { if(viz[i])continue; rec(i,i,0); } for(i=1;i<=m;i++) { if(rs[i]=='L' || rs[i]=='R')cout<<rs[i]; else cout<<'B'; } cout<<endl; return 0; }

Compilation message (stderr)

oneway.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
oneway.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void col(int)':
oneway.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void con(int)':
oneway.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void build(int, int)':
oneway.cpp:83:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void rec(int, int, int)':
oneway.cpp:105:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)
              ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...