Submission #35491

#TimeUsernameProblemLanguageResultExecution timeMemory
35491imaxblueOne-Way Streets (CEOI17_oneway)C++14
100 / 100
769 ms44788 KiB
#include <iostream> #include<bits/stdc++.h> using namespace std; #define pii pair<int, int> #define pb push_back #define x first #define y second #define lb lower_bound #define mp make_pair int n, m, p, com[100005], pre[100005], num[100005], c, a, b; int par[20][100005], d[100005], one[100005], dir[100005]; vector<pii> st[100005]; vector<pii> v[100005], w[100005]; vector<int> vis; void dfs(int N, int P){ if (num[N]!=0) return; num[N]=(pre[N]=++c); //if (num[N]==1) exit(2); vis.pb(N); for (int l=0; l<v[N].size(); ++l){ if (v[N][l].x==P) {P=-1; continue;} dfs(v[N][l].x, N); pre[N]=min(pre[N], pre[v[N][l].x]); } if (pre[N]==num[N]){ int t=-1; do{ t=vis.back(); vis.pop_back(); com[t]=N; //cout << N << ' ' << t << endl; for (int l=0; l<v[t].size(); ++l){ w[N].pb(v[t][l]); } } while(t!=N); } } void dfs2(int N, int P){ N=com[N]; if (P==-1) d[N]=1; else d[N]=d[P]+1; for (int l=0; l<20; ++l) par[l][N]=-1; par[0][N]=P; int k=0; while(par[k][N]!=-1){ par[k+1][N]=par[k][par[k][N]]; ++k; } for (int l=0; l<w[N].size(); ++l){ w[N][l].x=com[w[N][l].x]; if (w[N][l].x==N || w[N][l].x==P) continue; dfs2(w[N][l].x, N); } } void lca(int a, int b){ int A=(a=com[a]), B=(b=com[b]), k=19; if (a==b) return; while(d[A]>d[B]){ //cout << A << ' ' << d[A] << endl; while(k>0 && (d[A]-(1 << k)<d[B])) k--; A=par[k][A]; } while(d[B]>d[A]){ //cout << B << ' ' << d[B] << endl; while(k>0 && (d[B]-(1 << k)<d[A])) k--; B=par[k][B]; } k=19; while(A!=B){ while(k>0 && par[k][A]==par[k][B]){ --k; } A=par[k][A]; B=par[k][B]; //cout << k << ' ' << A << ' ' << B << endl; } //cout << A << ' ' <<B << endl;return; st[a].pb(mp(A, 1)); st[b].pb(mp(A, 0)); //cout << a << ' ' << A << ' ' << b << endl; } multiset<int> s[2]; void dfs3(int N, int P){ N=com[N]; com[N]=0; for (int l=0; l<st[N].size(); ++l){ s[st[N][l].y].insert(st[N][l].x); } //cout << N << ' ' << s[0].size()<< ' ' << s[1].size() << endl; int a, b, t; for (int l=0; l<w[N].size(); ++l){ if (w[N][l].x==N || w[N][l].x==P) continue; a=s[0].size(); b=s[1].size(); dfs3(w[N][l].x, N); t=0; //if (s[0].size()>a && s[1].size()>b) exit(1); if (s[0].size()>a) t=1; if (s[1].size()>b) t=2; if (w[N][l].y<0){ t=(3-t)%3; w[N][l].y*=-1; } //cout << N << ' ' << w[N][l].x << ' ' << P << ' ' << t << ' ' << w[N][l].y << endl; dir[w[N][l].y]=t; } s[0].erase(N); s[1].erase(N); } int dist[100005][2], r[100005]; queue<pii> q; bool dfs4(int N, int P, int D){ N=com[N]; num[N]=0; if (N==D) return 1; for (int l=0; l<w[N].size(); ++l){ w[N][l].x=com[w[N][l].x]; if (w[N][l].x==P || w[N][l].x==N) continue; if (dfs4(w[N][l].x, N, D)){ //cout << N << ' ' << w[N][l].x << endl; dir[abs(w[N][l].y)]=(w[N][l].y<0)+1; //cout << "*" << endl; return 1; } } return 0; } void bfs(int A, int B){ dfs4(com[A], -1, com[B]); } int main() { cin >> n >> m; for (int l=0; l<m; ++l){ cin >> a >> b; v[a].pb(mp(b, l+1)); v[b].pb(mp(a, -l-1)); } for (int l=1; l<=n; ++l) if (num[l]==0) dfs(l, -1); cin >> p; if (p<=100 && 0){ for (int l=0; l<p; ++l){ cin >> a >> b; bfs(a, b); } } else { for (int l=1; l<=n; ++l) if (par[0][com[l]]==0) dfs2(com[l], -1); for (int l=0; l<p; ++l){ cin >> a >> b; lca(a, b); } for (int l=1; l<=n; ++l) if (num[com[l]]!=0) dfs3(com[l], -1); } for (int l=1; l<=m; ++l){ if (dir[l]==0) cout << "B"; else if (dir[l]==1) cout << "R"; else if (dir[l]==2) cout << "L"; else return 1; } return 0; }

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<v[N].size(); ++l){
                    ^
oneway.cpp:31:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int l=0; l<v[t].size(); ++l){
                            ^
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<w[N].size(); ++l){
                    ^
oneway.cpp: In function 'void dfs3(int, int)':
oneway.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<st[N].size(); ++l){
                    ^
oneway.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<w[N].size(); ++l){
                    ^
oneway.cpp:92:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (s[0].size()>a) t=1;
                        ^
oneway.cpp:93:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (s[1].size()>b) t=2;
                        ^
oneway.cpp: In function 'bool dfs4(int, int, int)':
oneway.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<w[N].size(); ++l){
                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...