#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
const int LOG = 20;
const int N = 1e5 + 7;
vector<pair<int, int>> adj[N];
vector<pair<int, int>> g[N];
int n, m;
int num_comps;
int comps[N];
int num[N];
int low[N];
int timer;
int depth[N];
int par[N][LOG + 1];
bool R[N], L[N];
int sum_R[N], sum_L[N];
stack<int> st;
pair<int, int> e[N];
void dfs1(int u, int p) {
num[u] = low[u] = ++ timer;
st.push(u);
for (pair<int, int> v: adj[u]) if (v.se != p) {
if (num[v.fi]) {
minimize(low[u], num[v.fi]);
} else {
dfs1(v.fi, v.se);
minimize(low[u], low[v.fi]);
}
}
if (low[u] == num[u]) {
int v;
num_comps ++;
do {
v = st.top();
st.pop();
low[v] = num[v] = N;
comps[v] = num_comps;
} while (u != v);
}
}
void dfs2(int u, int p) {
par[u][0] = p;
for (int i = 1; i <= LOG; i ++) {
par[u][i] = par[par[u][i - 1]][i - 1];
}
for (pair<int, int> v: g[u]) if (v.fi != p) {
depth[v.fi] = depth[u] + 1;
dfs2(v.fi, u);
}
}
int lca(int u, int v) {
if (depth[v] > depth[u]) {
swap(u, v);
}
int dist = depth[u] - depth[v];
for (int i = LOG; i >= 0; i --) if ((dist >> i) & 1) {
u = par[u][i];
}
if (u == v) {
return u;
}
for (int i = LOG; i >= 0; i --) if (par[u][i] != par[v][i]) {
u = par[u][i];
v = par[v][i];
}
return par[u][0];
}
void build_tree() {
for (int u = 1; u <= n; u ++) {
for (pair<int, int> v: adj[u]) {
if (comps[v.fi] != comps[u]) {
g[comps[u]].emplace_back(comps[v.fi], v.se);
}
}
}
dfs2(1, 1);
}
void dfs3(int u, int p) {
for (pair<int, int> v: g[u]) if (v.fi != p) {
dfs3(v.fi, u);
int f, t; tie(f, t) = e[v.se];
bool dir = (u == comps[f] && v.fi == comps[t]);
// if (u == 1) {
// cout << comps[f] << " " << comps[t] << '\n';
// }
if (sum_R[v.fi]) {
(dir ? R[v.se] = true : L[v.se] = true);
}
if (sum_L[v.fi]) {
(dir ? L[v.se] = true : R[v.se] = true);
}
sum_L[u] += sum_L[v.fi];
sum_R[u] += sum_R[v.fi];
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= m; i ++) {
int u, v; cin >> u >> v;
e[i] = mp(u, v);
adj[u].emplace_back(v, i);
adj[v].emplace_back(u, i);
}
for (int i = 1; i <= n; i ++) {
if (!num[i]) {
assert(i == 1);
dfs1(i, 0);
}
}
build_tree();
// for (int i = 1; i <= n; i ++) {
// cerr << i << " -> " << comps[i] << '\n';
// }
int q; cin >> q;
for (int i = 1; i <= q; i ++) {
int u, v; cin >> u >> v;
u = comps[u];
v = comps[v];
int w = lca(u, v);
// u -> w -> v
sum_L[u] ++;
sum_L[w] --;
sum_R[v] ++;
sum_R[w] --;
// cerr << w << '\n';
}
dfs3(1, -1);
for (int i = 1; i <= m; i ++) {
// cerr << L[i] << " " << R[i] << '\n';
if (L[i] + R[i] != 1) {
cout << "B";
} else {
cout << (R[i] ? "R" : "L");
}
// cerr << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
10068 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
10068 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
10068 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
