Submission #124972

#TimeUsernameProblemLanguageResultExecution timeMemory
124972semiautoOne-Way Streets (CEOI17_oneway)C++14
0 / 100
9 ms5468 KiB
#include <bits/stdc++.h> using namespace std; int n,m,a,b,t,i,who,k,q; char ch[100001]; vector <int> v[100001]; vector <pair <int,pair <int,int> > > gr[100001]; bool fix[100001],block[100001],isbridge[100001]; int tin[100001],low[100001],parent[100001],in[100001],out[100001],aloup[100001],alodown[100001],A[100001],B[100001],p[100001][17]; map <pair<int,int>,int> mymap; void dfsjust(int a,int c) { parent[a]=c; int i; for (i=0;i<v[a].size();i++) { if (parent[v[a][i]] && parent[v[a][i]]!=c && isbridge[mymap[{a,v[a][i]}]]) { gr[c].push_back({parent[v[a][i]],{a,v[a][i]}}); gr[parent[v[a][i]]].push_back({c,{v[a][i],a}}); } if (!parent[v[a][i]] && !isbridge[mymap[{a,v[a][i]}]]) dfsjust(v[a][i],c); } } void justdfs(int a) { fix[a]=1; int i; for (i=0;i<v[a].size();i++) if (!fix[v[a][i]]) justdfs(v[a][i]); } void dfs(int a,int b) { fix[a]=1; tin[a]=low[a]=t++; int i; for (i=0;i<v[a].size();i++) { if (v[a][i]==b) continue; if (fix[v[a][i]]) low[a]=min(low[a],tin[v[a][i]]); else { dfs(v[a][i],a); low[a]=min(low[a],low[v[a][i]]); if (low[v[a][i]]>tin[a]) isbridge[mymap[{a,v[a][i]}]]=1; } } } void go(int a,int b) { in[a]=t++; p[a][0]=b; int i; for (i=1;i<17;i++) p[a][i]=p[p[a][i-1]][i-1]; for (i=0;i<gr[a].size();i++) if (gr[a][i].first!=b) go(gr[a][i].first,a); out[a]=t++; } bool isp(int a,int b) { if (in[a]<=in[b] && out[a]>=out[b]) return true; return false; } int lca(int c,int b) { int x=1,i; for (i=16;i>=0;i--) if (p[c][i] && !isp(p[c][i],b)) { c=p[c][i]; x+=(1<<i); } return x; } void gogo(int a,int b) { int i; for (i=0;i<gr[a].size();i++) if (gr[a][i].first!=b) { if (aloup[gr[a][i].first] || alodown[gr[a][i].first]) { int hey=mymap[{gr[a][i].second.first,gr[a][i].second.second}]; if (aloup[gr[a][i].first]) swap(A[hey],B[hey]); if (gr[a][i].second.second==B[hey]) ch[hey]='R'; else ch[hey]='L'; } gogo(gr[a][i].first,a); } } int goup(int a,int b) { int i,x=0; for (i=0;i<gr[a].size();i++) if (gr[a][i].first!=b) x=max(x,goup(gr[a][i].first,a)); return aloup[a]=max(aloup[a],x-1); } int godown(int a,int b) { int i,x=0; for (i=0;i<gr[a].size();i++) if (gr[a][i].first!=b) x=max(x,godown(gr[a][i].first,a)); return alodown[a]=max(alodown[a],x-1); } int main() { cin>>n>>m; for (i=1;i<=m;i++) { ch[i]='B'; cin>>a>>b; A[i]=a;B[i]=b; if (a==b) continue; if (mymap[{a,b}]) block[mymap[{a,b}]]=block[mymap[{b,a}]]=1; else { v[a].push_back(b); v[b].push_back(a); mymap[{a,b}]=mymap[{b,a}]=i; } } for (i=1;i<=n;i++) { if (!fix[i]) justdfs(i); else continue; if (who) { v[who].push_back(i); v[i].push_back(who); } else who=i; } for (i=1;i<=n;i++) fix[i]=0; for (i=1;i<=n;i++) if (!fix[i]) dfs(i,-1); for (i=1;i<=n;i++) if (!parent[i]) dfsjust(i,++k); go(1,0); cin>>q; for (i=1;i<=q;i++) { cin>>a>>b; a=parent[a]; b=parent[b]; if (!isp(a,b)) aloup[a]=max(aloup[a],lca(a,b)); if (!isp(b,a)) alodown[b]=max(alodown[b],lca(b,a)); } aloup[1]=goup(1,0); alodown[1]=godown(1,0); gogo(1,0); for (i=1;i<=m;i++) { if (block[mymap[{a,b}]]) ch[i]='B'; cout<<ch[i]; } cout<<endl; }

Compilation message (stderr)

oneway.cpp: In function 'void dfsjust(int, int)':
oneway.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[a].size();i++) {
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void justdfs(int)':
oneway.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[a].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[a].size();i++) {
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void go(int, int)':
oneway.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<gr[a].size();i++)
              ~^~~~~~~~~~~~~
oneway.cpp: In function 'void gogo(int, int)':
oneway.cpp:73:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<gr[a].size();i++)
              ~^~~~~~~~~~~~~
oneway.cpp: In function 'int goup(int, int)':
oneway.cpp:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<gr[a].size();i++)
              ~^~~~~~~~~~~~~
oneway.cpp: In function 'int godown(int, int)':
oneway.cpp:97:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<gr[a].size();i++)
              ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...