Submission #858390

#TimeUsernameProblemLanguageResultExecution timeMemory
858390Tenis0206One-Way Streets (CEOI17_oneway)C++11
0 / 100
2 ms10588 KiB
#include <bits/stdc++.h> using namespace std; const int nmax = 1e5; const int oo = INT_MAX; int n,m,k; pair<int,int> e[nmax + 5]; vector<pair<int,int>> G[nmax + 5]; bool sel[nmax + 5]; int lvl[nmax + 5], r[nmax + 5]; int p[nmax + 5], u[nmax + 5]; vector<pair<int,int>> rst; vector<int> out[nmax + 5], in[nmax + 5]; int cnt = 0; char rez[nmax + 5]; vector<int> l_sel; int Min_px[nmax + 5], Max_px[nmax + 5], Min_py[nmax + 5], Max_py[nmax + 5]; void dfs(int nod, int nr = 0) { l_sel.push_back(nod); p[nod] = (++cnt); sel[nod] = true; r[nod] = lvl[nod]; for(auto it : G[nod]) { if(sel[it.first]) { if(it.second!=nr) { r[nod] = min(r[nod], lvl[it.first]); } continue; } lvl[it.first] = 1 + lvl[nod]; dfs(it.first,it.second); r[nod] = min(r[nod], r[it.first]); } u[nod] = cnt; } void solve(int nod, int nr = 0) { sel[nod] = true; for(auto it : G[nod]) { if(sel[it.first]) { if(it.second!=nr) { rez[it.second] = 'B'; } continue; } solve(it.first,it.second); } Min_px[nod] = oo, Max_px[nod] = 0, Min_py[nod] = oo, Min_px[nod] = 0; for(auto x : in[nod]) { Min_px[nod] = min(Min_px[nod], p[x]); Max_px[nod] = max(Max_px[nod], p[x]); } for(auto y : out[nod]) { Min_py[nod] = min(Min_py[nod], p[y]); Max_py[nod] = max(Max_py[nod], p[y]); } for(auto it : G[nod]) { if(sel[it.first]) { continue; } Min_px[nod] = min(Min_px[nod], Min_px[it.first]); Max_px[nod] = max(Max_px[nod], Max_px[it.first]); Min_py[nod] = min(Min_py[nod], Min_py[it.first]); Max_py[nod] = max(Max_py[nod], Max_py[it.first]); } if(!nr) { return; } if(r[nod] < lvl[nod]) { rez[nr] = 'B'; return; } bool sus = false, jos = false; if(Min_px[nod] < p[nod] || Max_px[nod] > u[nod]) { jos = true; } if(Min_py[nod] < p[nod] || Max_py[nod] > u[nod]) { sus = true; } if(jos) { if(e[nr].second == nod) { rez[nr] = 'R'; } else { rez[nr] = 'L'; } } if(sus) { if(e[nr].second == nod) { rez[nr] = 'L'; } else { rez[nr] = 'R'; } } if(!sus && !jos) { rez[nr] = 'B'; } } int main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef home freopen("nr.in","r",stdin); freopen("nr.out","w",stdout); #endif // home cin>>n>>m; for(int i=1; i<=m; i++) { int x,y; cin>>x>>y; e[i] = {x,y}; if(x==y) { rez[i] = 'B'; continue; } G[x].push_back({y,i}); G[y].push_back({x,i}); } cin>>k; for(int i=1; i<=k; i++) { int x,y; cin>>x>>y; out[x].push_back(y); in[y].push_back(x); rst.push_back({x,y}); } for(int i=1; i<=n; i++) { if(!sel[i]) { l_sel.clear(); dfs(i); for(auto it : l_sel) { sel[it] = false; } solve(i); } } cout<<rez+1<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...