#include <bits/stdc++.h>
template <class T> using Vec = std::vector<T>;
int main() {
int N, M;
std::cin >> N >> M;
Vec<Vec<int>> graph(N);
std::map<std::pair<int, int>, int> eid;
std::map<std::pair<int, int>, bool> rev;
for (int i = 0; i < M; ++i) {
int x, y;
std::cin >> x >> y;
x -= 1;
y -= 1;
graph[x].push_back(y);
graph[y].push_back(x);
eid[{x, y}] = eid[{y, x}] = i;
rev[{y, x}] = true;
}
Vec<Vec<int>> children(N);
Vec<int> sum(N), parent(N), depth(N, -1);
auto dfs = [&](auto&& dfs, const int u) -> void {
for (const int v : graph[u]) {
if (v != parent[u]) {
if (depth[v] == -1) {
parent[v] = u;
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] = parent;
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&& dfs, const int u) -> void {
for (const int v : children[u]) {
dfs(dfs, 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 std::pair<int, int> e(u, parent[u]);
if (xs[u] > 0) {
ans[eid[e]] = rev[e] ? 'L' : 'R';
}
if (ys[u] > 0) {
ans[eid[e]] = rev[e] ? 'R' : 'L';
}
}
}
std::cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
