#include <bits/stdc++.h>
template <class T> using Vec = std::vector<T>;
int main() {
int N, M;
std::cin >> N >> M;
Vec<Vec<std::pair<int, int>>> graph(N);
Vec<int> A(M), B(M);
for (int i = 0; i < M; ++i) {
std::cin >> A[i] >> B[i];
A[i] -= 1;
B[i] -= 1;
graph[A[i]].emplace_back(B[i], i);
graph[B[i]].emplace_back(A[i], i);
}
Vec<Vec<int>> children(N);
Vec<int> sum(N), parent(N, -1), depth(N, -1);
auto dfs = [&](auto&& dfs, const int u) -> void {
for (const auto [v, e] : graph[u]) {
if (e != parent[u]) {
if (depth[v] == -1) {
parent[v] = e;
depth[v] = depth[u] + 1;
children[u].push_back(v);
dfs(dfs, v);
sum[u] += sum[v];
} else if (depth[v] < depth[u]) {
sum[u] += 1;
sum[v] -= 1;
}
}
}
};
depth[0] = 0;
dfs(dfs, 0);
std::array<Vec<int>, 17> lift;
lift[0].resize(N);
lift[0][0] = 0;
for (int i = 1; i < N; ++i) {
lift[0][i] = (A[parent[i]] == i ? B[parent[i]] : A[parent[i]]);
}
for (int i = 0; i < 16; ++i) {
lift[i + 1].resize(N);
for (int j = 0; j < N; ++j) {
lift[i + 1][j] = lift[i][lift[i][j]];
}
}
const auto lca = [&](int x, int y) {
if (depth[x] > depth[y]) {
std::swap(x, y);
}
const int dif = depth[y] - depth[x];
for (int i = 0; i < 17; ++i) {
if (dif >> i & 1) {
y = lift[i][y];
}
}
if (x == y) {
return x;
}
for (int i = 16; i >= 0; --i) {
if (lift[i][x] != lift[i][y]) {
x = lift[i][x];
y = lift[i][y];
}
}
return lift[0][x];
};
int P;
std::cin >> P;
Vec<int> xs(N), ys(N);
for (int i = 0; i < P; ++i) {
int x, y;
std::cin >> x >> y;
x -= 1;
y -= 1;
const int z = lca(x, y);
xs[x] += 1;
xs[z] -= 1;
ys[y] += 1;
ys[z] -= 1;
}
auto count = [&](auto&& count, const int u) -> void {
for (const int v : children[u]) {
count(count, v);
xs[u] += xs[v];
ys[u] += ys[v];
}
};
count(count, 0);
std::string ans(M, 'B');
for (int u = 1; u < N; ++u) {
if (sum[u] == 0) {
const int e = parent[u];
if (xs[u] > 0) {
ans[e] = (B[e] == u) ? 'L' : 'R';
}
if (ys[u] > 0) {
ans[e] = (B[e] == u) ? 'R' : 'L';
}
}
}
std::cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
