#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> p, d, tin, tout;
int timer;
void fill(int v, int pr){
tin[v] = ++timer;
p[v] = pr;
for (int i: g[v]){
if (i == pr) continue;
d[i] = d[v] + 1;
fill(i, v);
}
tout[v] = timer;
}
vector<int> f;
vector<bool> b;
void build(){
p.resize(n + 1);
d.resize(n + 1);
tin.resize(n + 1);
tout.resize(n + 1);
timer = 0;
fill(1, 0);
f.resize(n + 1);
b.resize(n + 1);
for (auto [x, y]: ed){
// x -> y : L -> R
if (d[x] > d[y]){
b[x] = 1;
}
else {
b[y] = 0;
}
}
}
bool check(int x, int y){
return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}
int lca(int x, int y){
while (!check(x, y)){
x = p[x];
}
return x;
}
void set_r(int x, int l, bool i){
while (x != l){
int val = 1 + (b[x] ^ i);
if (f[x] && f[x] != val){
while (true){
x++;
}
}
f[x] = val;
x = p[x];
}
}
void setp(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);
}
};
dfs(1);
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);
}
};
fill_d(1, 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});
}
};
solve(1, 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);
}
}
TR T(cnt);
assert((cnt == (br.size() + 1)));
map<pii, bool> mp;
for (auto [x, y]: br){
x = gr[x]; y = gr[y];
mp[{x, y}] = 1;
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.setp(x, y);
}
for (auto [x, y]: ed){
x = gr[x]; y = gr[y];
if (x == y){
cout<<'B';
continue;
}
// assert((mp.find({x, y}) != mp.end() || mp.find({y, x}) != mp.end()));
cout<<T.get(x, y);
}
cout<<"\n";
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from oneway.cpp:1:
oneway.cpp: In function 'int main()':
oneway.cpp:174:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | assert((cnt == (br.size() + 1)));
| ~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
