제출 #550346

#제출 시각아이디문제언어결과실행 시간메모리
550346leakedOne-Way Streets (CEOI17_oneway)C++17
0 / 100
12 ms23764 KiB
#include <bits/stdc++.h> #define f first #define s second #define m_p make_pair #define vec vector #define pb push_back #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define pw(x) (1LL<<(x)) #define sz(x) (int)(x).size() using namespace std; typedef long long ll; typedef pair<int,int> pii; template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);} template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);} const int N=5e5+1; vec<array<int,3>> g[N]; int in[N],out[N],tt=1,fup[N],up[N][20]; char clr[N]; bool is(int a,int b){ return in[a]<=in[b]&&out[a]>=out[b]; } vec<array<int,3>> gr[N]; void dfs(int v,int p,int pr){ in[v]=fup[v]=tt++; up[v][0]=pr; for(int i=1;i<20;i++) up[v][i]=up[up[v][i-1]][i-1]; for(auto &z : g[v]){ if(z[1]==p) continue; if(in[z[0]]){ umin(fup[v],in[z[0]]); if(in[z[0]]<in[v]) cout<<"E! "<<v<<' '<<z[0]<<endl; clr[z[1]]='B'; } else{ // cout<<"E "<<v<<' '<<z[0]<<endl; dfs(z[0],z[1],v); gr[v].pb(z); umin(fup[v],fup[z[0]]); // cout<<"E "<<v<<' '<<z[0]<<' '<<in[v]<<' '<<fup[z[0]]<<endl; if(fup[z[0]]<=in[v]) clr[z[1]]='B'; else clr[z[1]]='.'; } } out[v]=tt-1; } int dp[N][2]; string fck="LR"; void dfs2(int v){ for(auto &z : gr[v]){ dfs2(z[0]); for(int t=0;t<2;t++) dp[v][t]+=dp[z[0]][t]; // cout<<dp[z[0]][0]<<' '<< if(dp[z[0]][0] || dp[z[0]][1]){ if(clr[z[1]]=='B') continue; if(dp[z[0]][0]) clr[z[1]]=fck[0^z[2]^1]; else clr[z[1]]=fck[1^z[2]^1]; } else clr[z[1]]='B'; } } int lca(int a,int b){ if(is(a,b)) return a; for(int i=19;i>=0;i--){ if(!is(up[a][i],b)) a=up[a][i]; } return up[a][0]; } signed main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n,m; cin>>n>>m; for(int i=0;i<m;i++){ int v,u; cin>>v>>u;--v;--u; g[v].pb({u,i,0}); g[u].pb({v,i,1}); } vec<int>roots; for(int i=0;i<n;i++){ if(!in[i]) roots.pb(i),dfs(i,-1,i); } int q; cin>>q; while(q--){ int v,u; cin>>v>>u;--v;--u; cerr<<"WO "<<v<<' '<<u<<' '<<lca(v,u)<<endl; dp[v][1]++; dp[u][0]++; dp[lca(v,u)][0]--; dp[lca(v,u)][1]--; } for(auto &z : roots) dfs2(z); for(int i=0;i<m;i++) cout<<clr[i]; return 0; } /* 10 10 1 6 5 5 1 1 4 2 4 2 10 3 1 3 8 9 8 9 7 6 8 3 9 8 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...