#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= l; --i)
#define ALL(x) (x).begin(), (x).end()
using i64 = long long;
vector<int> decomposite(const vector<vector<int>> &graph) {
const int n = (int)graph.size();
vector<bool> isUsed(n);
vector<int> ord(n), low(n);
auto dfs = [&](auto &&self, const int v, const int p, int &id) -> void {
isUsed[v] = true;
ord[v] = id++;
low[v] = ord[v];
for (const int t : graph[v]) {
if (isUsed[t]) {
if (t != p) low[v] = min(low[v], ord[t]);
continue;
}
self(self, t, v, id);
low[v] = min(low[v], low[t]);
}
};
int id = 0;
dfs(dfs, 0, -1, id);
vector<int> group(n, -1);
auto dfs2 = [&](auto &&self, const int v, const int p, int &id) -> void {
assert(group[v] == -1);
if (p != -1 and ord[p] >= low[v]) {
group[v] = group[p];
} else {
group[v] = id++;
}
for (const int t : graph[v]) {
if (group[t] != -1) continue;
self(self, t, v, id);
}
};
id = 0;
rep(i, 0, n) {
if (group[i] == -1) {
dfs2(dfs2, i, -1, id);
}
}
return group;
}
void main_() {
int N, M;
cin >> N >> M;
vector<int> A(M), B(M);
vector<vector<int>> graph(N);
rep(i, 0, M) {
cin >> A[i] >> B[i];
graph[--A[i]].push_back(--B[i]);
graph[B[i]].push_back(A[i]);
}
int P;
cin >> P;
vector<int> X(P), Y(P);
rep(i, 0, P) {
cin >> X[i] >> Y[i];
--X[i], --Y[i];
}
const auto group = decomposite(graph);
vector<char> ans(M, 'A');
rep(i, 0, M) {
if (group[A[i]] == group[B[i]]) {
ans[i] = 'B';
}
}
const int U = *max_element(ALL(group)) + 1;
vector<vector<pair<int, int>>> tree(U);
rep(i, 0, M) {
if (group[A[i]] != group[B[i]]) {
tree[group[A[i]]].push_back({group[B[i]], i});
tree[group[B[i]]].push_back({group[A[i]], i});
}
}
vector<vector<int>> F(N), T(N);
rep(i, 0, P) {
F[X[i]].push_back(i);
T[Y[i]].push_back(i);
}
vector<int> par(U, -1), depth(U);
constexpr int R = 20;
vector<vector<int>> table(R);
auto dfsC = [&](auto &&self, const int v, const int p, const int d) -> void {
par[v] = p;
depth[v] = d;
for (const auto &[t, i] : tree[v]) {
if (t == p) continue;
self(self, t, v, d + 1);
}
};
rep(i, 0, U) {
if (par[i] != -1) continue;
dfsC(dfsC, i, -1, 0);
}
table[0] = par;
rep(rank, 1, R) {
table[rank].assign(U, -1);
rep(i, 0, U) {
if (table[rank - 1][i] == -1) continue;
else table[rank][i] = table[rank][table[rank - 1][i]];
}
}
auto calcLCA = [&](int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
per(rank, 0, 20) {
const int a = table[rank][v];
if (a != -1 and depth[a] >= depth[u]) v = a;
}
if (u == v) return u;
per(rank, 0, 20) {
const int a = table[rank][u], b = table[rank][v];
if (a != b) {
u = a;
v = b;
}
}
return par[u];
};
vector<int> e1(U), e2(U);
rep(i, 0, P) {
const int lca = calcLCA(group[X[i]], group[Y[i]]);
++e1[group[X[i]]];
++e2[group[Y[i]]];
--e1[lca];
--e2[lca];
}
auto setVal = [&](int a, int b, int i, int v) {
if (group[A[i]] != a) {
// rev
if (v != 3) v ^= 3;
}
ans[i] = v == 1 ? 'R' : (v == 2 ? 'L' : 'B');
};
vector<bool> isUsed(U);
auto dfs = [&](auto &&self, const int v, const int p) -> pair<int, int> {
isUsed[v] = true;
pair<int, int> val = {e1[v], e2[v]};
for (const auto &[t, i] : tree[v]) {
if (t == p) continue;
const auto res = self(self, t, v);
{
if (res.first != 0) setVal(t, v, i, 1);
else if (res.second != 0) setVal(v, t, i, 1);
else setVal(v, t, i, 3);
}
val.first += res.first;
val.second += res.second;
}
return val;
};
rep(i, 0, U) {
if (not isUsed[i]) {
dfs(dfs, i, -1);
}
}
for (const auto e : ans) cout << e;
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
main_();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
