Submission #1005215

#TimeUsernameProblemLanguageResultExecution timeMemory
1005215emad234One-Way Streets (CEOI17_oneway)C++17
0 / 100
1 ms6744 KiB
#include "bits/stdc++.h" #define F first #define S second #define ll long long #define pii pair<ll,ll> const ll mxN = 1e5 + 5; const ll mod = 1e9 + 7; using namespace std; struct edge{ int first,id,second; }; vector<vector<edge>>v,tr; int p[mxN]; int ans[mxN]; bool vis[mxN]; int dep[mxN]; void calctr(int u){ vis[u] = 1; for(auto x : v[u]){ if(vis[x.F]) continue; tr[x.F].push_back({u,x.id,!x.S}); tr[u].push_back(x); calctr(x.F); } } int n,m,pr; int g[mxN],t[mxN]; int ng[mxN],nt[mxN]; set<int>s[mxN]; void merge(int a, int b){ if(s[a].size() < s[b].size()) swap(s[a],s[b]); while(s[b].size()){ int u = *(s[b].begin()); if(g[u]){ if(s[a].find(g[u]) != s[a].end()) nt[a]--; else ng[a]++; } if(t[u]){ if(s[a].find(t[u]) != s[a].end() )ng[a]--; else nt[a]++; } s[a].insert(*(s[b].begin())); s[b].erase(s[b].begin()); } } void dfs(int u,int par,int ty,int id){ dep[u] = dep[par] + 1; for(auto x : tr[u]){ if(x.F == par) continue; dfs(x.F,u,!x.S,x.id); } s[u].insert(u); for(auto x : tr[u]){ if(x.F == par) continue; merge(u,x.F); } ng[par] += ng[u]; nt[par] += nt[u]; if(p[u] == 0) p[u] = m; int cnt = 0; for(auto x : v[u]) {if(x.F != par) p[u] = min(dep[x.F],p[u]); else cnt++;} // cout<<u<<' '<<nt[u]<<' '<<ng[u]<<' '<<p[u]<<' '<<par<<'\n'; if(p[par] == 0) p[par] = m; p[par] = min(p[u],p[par]); // cout<<u<<' '<<p[u]<<'\n'; if(p[u] >= dep[u]){ if(ng[u]) ans[id] = ty + 1; else if(nt[u]) ans[id] = (!ty) + 1; } } signed main(){ // ios_base::sync_with_stdio(0); // cin.tie(0); // cout.tie(0); cin >>n>>m; v.resize(n + 4); tr.resize(n + 4); for(int i = 1;i <= m;i++){ int x,y; cin >>x>>y; v[x].push_back({y,i, 0}); v[y].push_back({x,i, 1}); } cin >>pr; for(int i = 0;i < pr;i++){ int x,y; cin >>x>>y; g[x] = y; t[y] = x; } calctr(1); // cout<<"TEST\n"; memset(vis,0,sizeof vis); dfs(1,0,0,0); // for(int i = 1;i <= m;i++) cout<<ans[i]<<' '; // cout<<'\n'; for(int i = 1;i <= m;i++) cout<<(ans[i] == 0 ? 'B' : (ans[i] == 1 ? 'R' : 'L')); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...