| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1116964 | Sunbae | One-Way Streets (CEOI17_oneway) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define mp std::make_pair
#define F first
#define S second
#define N 100000
#define dN 200000
using pii = std::pair<int,int>;
std::vector<int> g[N];
int d[N], dp[N], tin[N], low[N], br[N], cnt[N], mn[N], C[N], e[dN], t[dN], st[N][18], cp_sz, mm, ti = 1, c = 1;
pii cp[N], E[N];
int P(int x, int y){ return std::lower_bound(cp, cp+cp_sz, mp(x, y)) - cp;}
void dfs(int u, int p = -1){
tin[u] = low[u] = ti++;
if(p != -1) d[u] = d[p] + 1;
for(int v: g[u]){
if(v != p){
if(!tin[v]){
dfs(v, u); low[u] = std::min(low[u], low[v]);
if(low[v] > tin[u] && cnt[P(u, v)] == 1) br[P(u, v)] = 1;
}else{
low[u] = std::min(low[u], tin[v]);
}
}
}
}
void efs(int u){
C[u] = c;
for(int v: g[u]){
int x = std::min(u, v), y = std::max(u, v);
if(!br[P(x, y)] && !C[v]) efs(v);
}
}
void ffs(int u, int p = -1){
tin[u] = 1; e[mm++] = u;
for(int v: g[u]) if(v != p) ffs(v, u), e[mm++] = u;
}
void gfs(int u, int p = -1){
tin[u] = 1;
for(int v: g[u]) if(v != p) gfs(v, u), dp[u] += dp[v];
}
signed main(){
int n, m; scanf("%d %d", &n, &m);
for(int i = 0, u, v, x, y; i<m; E[i++] = {u, v}){
scanf("%d %d", &u, &v); --u; --v;
cp[i] = {std::min(u, v), std::max(u, v)};
g[u].push_back(v); g[v].push_back(u);
}
std::sort(cp, cp+m); cp_sz = std::unique(cp, cp+m) - cp;
for(int i = 0; i<n; ++i){
std::sort(g[i].begin(), g[i].end());
g[i].resize(std::unique(g[i].begin(), g[i].end()) - g[i].begin());
}
for(int i = 0, x, y; i<m; ++i){
if((x = E[i].F) > (y = E[i].S)) std::swap(x, y);
++cnt[P(x, y)];
}
for(int i = 0; i<n; ++i) if(!tin[i]) dfs(i);
for(int i = 0; i<n; ++i) if(!C[i]) efs(i), ++c;
for(int i = 0; i<n; --C[i++]) g[i].clear(); --c;
for(int i = 0, u, v; i<m; ++i){
if(C[u = E[i].F] == C[v = E[i].S]) continue;
g[C[u]].push_back(C[v]); g[C[v]].push_back(C[u]);
}
for(int i = 0; i<c; tin[i++] = 0){
std::sort(g[i].begin(), g[i].end());
g[i].resize(unique(g[i].begin(), g[i].end()) - g[i].begin());
}
for(int i = 0; i<c; ++i) if(!tin[i]) ffs(i);
for(int i = mm-1; ~i; --i) t[mn[e[i]] = i] = e[i];
for(int i = 0; i<mm; ++i) st[i][0] = mn[e[i]];
for(int j = 1; j<32 - __builtin_clz(mm); ++j){
for(int i = 0; i+(1<<j)-1<mm; ++j) st[i][j] = std::min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}
int p; scanf("%d", &p);
for(int i = 0, u, v; i<p; ++i){
scanf("%d %d", &u, &v);
if(mn[u = C[--u]] > mn[v = C[--v]]) std::swap(u, v);
int j = 31 - __builtin_clz(mn[v]-mn[u]+1);
int lca = t[std::min(st[mn[u]][j], st[mn[v]-(1<<j)+1][j])];
++dp[u]; --dp[lca];
--dp[v]; ++dp[lca];
}
std::fill(tin, tin+c, 0);
for(int i = 0; i<c; ++i) if(!tin[i]) gfs(i);
for(int i = 0; i<m; ++i){
int u = E[i].F, v = E[i].S, x = std::min(u, v), y = std::max(u, v);
if(!br[P(x, y)]){ printf("B"); continue;}
if(d[v = C[v]] > d[u = C[u]]){
if(dp[v] > 0) printf("L");
else if(dp[v] < 0) printf("R");
else printf("B");
}else{
if(dp[u] > 0) printf("R");
else if(dp[u] < 0) printf("L");
else printf("B");
}
}
}