| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 994469 | vladilius | 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>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
struct TR{
vector<vector<int>> g;
vector<pii> ed;
int n;
TR(int ns){
n = ns;
g.resize(n + 1);
}
void add(int u, int v){
ed.pb({u, v});
g[u].pb(v);
g[v].pb(u);
}
vector<int> sz, h, p, d;
void fill(int v, int pr){
p[v] = pr;
sz[v] = 1;
for (int i: g[v]){
if (i == pr) continue;
d[i] = d[v] + 1;
fill(i, v);
if (sz[i] > sz[h[v]]){
h[v] = i;
}
sz[v] += sz[i];
}
}
vector<int> hd, pos;
int cnt;
void fill_hld(int v, int k){
pos[v] = ++cnt;
hd[v] = k;
if (!h[v]) return;
fill_hld(h[v], k);
for (int i: g[v]){
if (i != p[v] && i != h[v]){
fill_hld(i, i);
}
}
}
vector<int> f, inv;
vector<bool> b;
set<int> st;
void build(){
sz.resize(n + 1);
h.resize(n + 1);
p.resize(n + 1);
d.resize(n + 1);
fill(1, 0);
cnt = 0;
hd.resize(n + 1);
pos.resize(n + 1);
fill_hld(1, 1);
inv.resize(n + 1);
for (int i = 1; i <= n; i++){
inv[pos[i]] = i;
}
f.resize(n + 1);
for (int i = 2; i <= n; i++) st.ins(i);
b.resize(n + 1);
for (auto [x, y]: ed){
// x -> y
if (d[x] > d[y]){
b[x] = 1;
}
else {
b[y] = 0;
}
}
}
int lca(int x, int y){
while (hd[x] != hd[y]){
if (d[hd[x]] > d[hd[y]]){
swap(x, y);
}
y = p[hd[y]];
}
return ((d[x] > d[y]) ? y : x);
}
void upd(int l, int r, bool i){
if (l > r) return;
// cout<<"Yo "<<l<<" "<<b[l]<<" "<<i<<"\n";
auto it = st.lower_bound(l);
vector<int> er;
while (it != st.end() && *it <= r){
er.pb(*it++);
}
for (int j: er) st.erase(j);
for (int j: er){
// cout<<"Cool "<<inv[j]<<" "<<1 + (b[j] ^ i)<<"\n";
f[inv[j]] = 1 + (b[j] ^ i);
}
}
void set_r(int x, int l, bool i){
// cout<<"Hi "<<x<<" "<<l<<" "<<i<<"\n";
while (true){
if (d[l] < d[hd[x]]){
// hd[x] -> x
// x -> ... -> hd[x]
upd(pos[hd[x]], pos[x], i);
x = p[hd[x]];
}
else {
// l -> x
upd(pos[l] + 1, pos[x], i);
break;
}
}
}
void set(int x, int y){
int l = lca(x, y);
set_r(x, l, 0);
set_r(y, l, 1);
}
char get(int x, int y){
if (d[x] > d[y]) swap(x, y);
if (!f[y]) return 'B';
return ((f[y] == 1) ? 'L' : 'R');
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m; cin>>n>>m;
vector<pii> g[n + 1], ed;
for (int i = 1; i <= m; i++){
int u, v; cin>>u>>v;
ed.pb({u, v});
if (u == v) continue;
g[u].pb({v, i});
g[v].pb({u, i});
}
vector<bool> used(n + 1);
vector<int> t[n + 1], ind(n + 1);
function<void(int)> dfs = [&](int v){
used[v] = 1;
for (auto p: g[v]){
int i = p.ff;
if (used[i]) continue;
t[i].pb(v);
t[v].pb(i);
ind[i] = p.ss;
dfs(i);
}
};
for (int i = 1; i <= n; i++){
if (!used[i]){
dfs(i);
}
}
vector<int> d(n + 1, -1), par(n + 1);
function<void(int, int)> fill_d = [&](int v, int pr){
par[v] = pr;
for (int i: t[v]){
if (i == pr) continue;
d[i] = d[v] + 1;
fill_d(i, v);
}
};
for (int i = 1; i <= n; i++){
if (d[i] == -1){
fill_d(i, 0);
}
}
vector<int> dp(n + 1, -1);
vector<pii> br;
vector<bool> ban(m + 1);
function<void(int, int)> solve = [&](int v, int pr){
dp[v] = 0;
for (auto p: g[v]){
int i = p.ff;
if (i == pr || v == par[i]) continue;
dp[v] += (2 * (d[i] < d[v]) - 1);
}
for (int i: t[v]){
if (i == pr) continue;
solve(i, v);
dp[v] += dp[i];
}
if (!dp[v]){
ban[ind[v]] = 1;
if (v != 1) br.pb({v, pr});
}
};
for (int i = 1; i <= n; i++){
if (dp[i] == -1){
solve(i, 0);
}
}
fill(used.begin(), used.end(), 0);
vector<int> all[n + 1], gr(n + 1);
int cnt = 0;
function<void(int)> dfs1 = [&](int v){
all[cnt].pb(v);
gr[v] = cnt;
used[v] = 1;
for (auto [i, ii]: g[v]){
if (used[i] || ban[ii]) continue;
dfs1(i);
}
};
for (int i = 1; i <= n; i++){
if (!used[i]){
cnt++;
dfs1(i);
}
}
/*
cout<<"hey"<<"\n";
for (int i = 1; i <= cnt; i++){
for (int j: all[i]){
cout<<j<<" ";
}
cout<<"\n";
}
cout<<"hey"<<"\n";
*/
TR T(cnt);
for (auto [x, y]: br){
x = gr[x]; y = gr[y];
T.add(x, y);
}
T.build();
int q; cin>>q;
for (int i = 1; i <= q; i++){
int x, y; cin>>x>>y;
x = gr[x];
y = gr[y];
if (x != y) T.set(x, y);
}
for (auto [x, y]: ed){
x = gr[x]; y = gr[y];
if (x == y){
cout<<'B';
continue;
}
// cout<<'T';
cout<<T.get(x, y);
}
}