Submission #476355

#TimeUsernameProblemLanguageResultExecution timeMemory
476355cgiosyOne-Way Streets (CEOI17_oneway)C++17
100 / 100
64 ms11588 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0);cin.tie(0); int N, M, Q; cin>>N>>M; int E[M*2+2], F[M*2+2], G[N]{}; for(int i=1; i<=M; i++) { int a, b; cin>>a>>b; --a, --b; E[i*2]=b, F[i*2]=G[a], G[a]=i*2; E[i*2+1]=a, F[i*2+1]=G[b], G[b]=i*2+1; } int A[N]{}, T[N], P[N], t=0; char V[max(N, M)+1]{}; function<int(int)> root=[&](int i) { return P[i]>=0 ? P[i]=root(P[i]) : i; }; auto up=[&](int&i) { i=P[i]=root(~P[i]); }; function<void(int, int)> bcc=[&](int i, int p) { A[i]=T[i]=++t; for(int e=G[i]; e; e=F[e]) if(e!=p) { int&j=E[e]; if(A[j]) { T[i]=min(T[i], A[j]); continue; } V[e>>1]=e&1, P[j]=~i; bcc(j, e^1); T[i]=min(T[i], T[j]); if(A[i]<T[j]) V[e>>1]|=2; } }; for(int i=0; i<N; i++) if(!A[i]) P[i]=~i, bcc(i, 0); cin>>Q; while(Q--) { int i, j, a=4, b=8; cin>>i>>j; --i, --j; if(A[i]<A[j]) swap(i, j), swap(a, b); for(i=root(i); A[i]>A[j]; up(i)) V[i]|=a; for(j=root(j); A[j]>A[i]; up(j)) V[j]|=b; } for(int i=1; i<=M; i++) { int v=V[i], u=v&1, t=V[E[i*2^u]]>>2; cout<<((v&2) && t ? (t^u)&1 ? 'L' : 'R' : 'B'); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...