Submission #858382

#TimeUsernameProblemLanguageResultExecution timeMemory
858382Tenis0206One-Way Streets (CEOI17_oneway)C++11
0 / 100
2 ms9052 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]; void dfs(int nod, int nr = 0) { p[nod] = (++cnt); sel[nod] = true; r[nod] = oo; 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); } if(!nr) { return; } if(r[nod] < lvl[nod]) { rez[nr] = 'B'; return; } bool sus = false, jos = false; for(auto it : rst) { int x = it.first; int y = it.second; if((p[x] < p[nod] || p[x] > u[nod]) && (p[y] >= p[nod] && p[y] <= u[nod])) { jos = true; } if((p[y] < p[nod] || p[y] > u[nod]) && (p[x] >= p[nod] && p[x] <= 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'; } } } 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}); } dfs(1); for(int i=1;i<=n;i++) { sel[i] = false; } solve(1); cout<<rez+1<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...