#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5+5;
int n, m, q;
vector<int> g[mx];
bool vis[mx], vise[mx];
int dfn[mx], low[mx];
int t;
int ans[mx];
int p[30][mx];
int pe[mx];
int pp[mx];
int dep[mx];
// R = 1, L = 2, B = 3
struct Edge {
int u, v;
int id;
} e[mx];
void dfs1(int x, int pr, int d, int peg) {
dfn[x] = low[x] = ++t;
p[0][x] = pr;
dep[x] = d;
pe[x] = peg;
vis[x] = 1;
for (int i:g[x]) {
if (vise[i]) continue;
auto [u, v, id] = e[i];
if (u != x) swap(u, v);
if (!vis[v]) {
vise[i] = 1;
dfs1(v, x, d+1, i);
low[u] = min(low[u], low[v]);
} else {
low[u] = min(dfn[v], low[u]);
}
}
if (low[x] != dfn[x]) {
ans[peg] = 3;
}
}
void dfs2(int x, int la) {
vis[x] = 1;
if (ans[pe[x]] or x == 1) {
pp[x] = la;
} else {
pp[x] = x;
}
for (int i:g[x]) {
auto [u, v, id] = e[i];
if (u != x) swap(u, v);
if (vis[v]) continue;
dfs2(v, pp[x]);
}
}
void bdlca() {
for (int i=1;i<30;i++) {
for (int j=1;j<=n;j++) {
p[i][j] = p[i-1][p[i-1][j]];
}
}
}
int qlca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for (int i=29;~i;i--) if (d&(1<<i)) u = p[i][u];
if (u == v) return u;
for (int i = 29; ~i; i--) {
if (p[i][u] != p[i][v]) {
u = p[i][u]; v = p[i][v];
}
}
return p[0][u];
}
int main() {
// cin.tie(0);ios::sync_with_stdio(0);
cin >> n >> m;
for (int i=1;i<=m;i++) {
int u, v;
cin >> u >> v;
g[u].push_back(i);
g[v].push_back(i);
e[i] = {u, v, i};
}
dfs1(1, 0, 1, 0);
for (int i=1;i<=n;i++) {
vis[i] = 0;
}
dfs2(1, 0);
bdlca();
cin >> q;
while (q--) {
int u, v;
cin >> u >> v;
int lca = qlca(u, v);
vector<int> ve;
int lans = 0;
while (dep[pp[u]] > dep[lca]) {
ve.push_back(pp[u]);
ans[pe[pp[u]]] = 1;
u = p[0][pp[u]];
lans = pp[u];
}
for (int i:ve) {
pp[i] = lans;
}
ve.clear();
while (dep[pp[v]] > dep[lca]) {
ve.push_back(pp[v]);
ans[pe[pp[v]]] = 2;
v = p[0][pp[v]];
lans = pp[v];
}
for (int i:ve) {
pp[i] = lans;
}
}
for (int i=1;i<=m;i++) {
if (ans[i] == 0 or ans[i] == 3) {
cout << 'B';
} else if ( ans[i] == 1 ) {
if (dep[e[i].u] < dep[e[i].v]) {
cout << 'L';
} else {
cout << 'R';
}
} else {
if (dep[e[i].u] < dep[e[i].v] ){
cout << 'R';
} else {
cout << 'L';
}
}
}
cout << "\n";
}
Compilation message
oneway.cpp: In function 'void dfs1(int, int, int, int)':
oneway.cpp:31:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
31 | auto [u, v, id] = e[i];
| ^
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:54:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | auto [u, v, id] = e[i];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
33624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
33624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
33624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
