Submission #285990

#TimeUsernameProblemLanguageResultExecution timeMemory
285990BlagojceOne-Way Streets (CEOI17_oneway)C++11
0 / 100
3 ms5248 KiB
#include <bits/stdc++.h> #define fr(i, n, m) for(int i = (n); i < (m); i ++) #define pb push_back #define st first #define nd second #define pq priority_queue #define all(x) begin(x), end(x) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; const ll inf = 1e18; const ld eps = 1e-13; const ll mod = 1e9+7; const int i_inf = 1e9; const int mxn = 1e5; mt19937 _rand(time(NULL)); clock_t timer = clock(); int n, m; vector<pii> g[mxn]; int ans[mxn]; int dep[mxn]; bool vis[mxn]; bool bridge[mxn]; void dfs0(int u, int ed){ vis[u] = true; int mindepth = dep[u]; for(auto e : g[u]){ if(e.nd == ed) continue; if(!vis[e.st]){ dep[e.st] = dep[u] + 1; dfs0(e.st, e.nd); } mindepth = min(mindepth, dep[e.st]); } if(mindepth >= dep[u]){ bridge[ed] = true; } else{ dep[u] = mindepth; } } int group[mxn]; void dfs1(int u, int col){ vis[u] = true; group[u] = col; for(auto e : g[u]){ if(vis[e.st] || bridge[e.nd]) continue; dfs1(e.st, col); } } vector<pii> tree[mxn]; int par[mxn]; int uped[mxn]; int sparse[mxn][20]; int depth[mxn]; void dfs2(int u){ vis[u] = true; sparse[u][0] = par[u]; fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i-1]][i-1]; for(auto e : tree[u]){ if(vis[e.st]) continue; par[e.st] = u; depth[e.st] = depth[u] + 1; uped[e.st] = e.nd; dfs2(e.st); } } int lca(int a, int b){ int d = min(depth[a], depth[b]); for(int i = 19; i >= 0; i --){ if(depth[a] - (1<<i) >= d) a = sparse[a][i]; if(depth[b] - (1<<i) >= d) b = sparse[b][i]; } if(a == b) return a; for(int i = 19; i >= 0; i --){ if(sparse[a][i] != sparse[b][i]){ a = sparse[a][i]; b = sparse[b][i]; } } return sparse[a][0]; } void solve(){ cin >> n >> m; int l[m], r[m]; fr(i, 0, m){ int u, v; cin >> u >> v; --u, --v; l[i] = u; r[i] = v; if(u == v){ continue; } g[u].pb({v, i}); g[v].pb({u, i}); } fr(i, 0, n){ if(vis[i]) continue; dfs0(i, -1); } memset(vis, false, sizeof(vis)); int col = 0; fr(i, 0, n){ if(vis[i]) continue; dfs1(i, col); ++col; } fr(i, 0, m){ if(!bridge[i] || l[i] == r[i]) continue; int a = group[l[i]]; int b = group[r[i]]; tree[a].pb({b, i+1}); tree[b].pb({a, -(i+1)}); } memset(vis, false, sizeof(vis)); fr(i, 0, col){ if(vis[i]) continue; par[i] = i; uped[i] = 0; dfs2(i); } int p; cin >> p; bool answered[mxn]; memset(answered, false, sizeof(answered)); fr(i, 0, p){ int u, v; cin >> u >> v; --u, --v; u = group[u]; v = group[v]; if(u == v) continue; int k = lca(u, v); while(!answered[u] && depth[u] > depth[k]){ if(uped[u] == 0) break; if(uped[u] < 0){ ans[(-uped[u])-1] = 1; } else{ ans[uped[u]-1] = 2; } answered[u] = true; u = par[u]; } while(!answered[v] && depth[v] > depth[k]){ if(uped[v] == 0) break; if(uped[v] < 0){ ans[(-uped[v])-1] = 2; } else{ ans[uped[v]-1] = 1; } answered[v] = true; v = par[v]; } } fr(i, 0, m){ if(ans[i] == 0) cout<<'B'; else if(ans[i] == 1) cout<<'R'; else cout<<'L'; } cout<<endl; } int main(){ solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...