#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
template<typename T>
bool ckmn(T &x, T y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template<typename T>
bool ckmx(T &x, T y) {
if (x < y) {
x = y;
return true;
}
return false;
}
const int N = 100001, infI = 1e9 + 7;
const ll infL = 3e18;
int n, m, k;
int A[N], B[N], X[N], Y[N], tin[N], fup[N], T = 0, color[N], parent[N], jump[N], depth[N], idx_par[N];
bool bridge[N], used[N];
vector<pair<int, int>> g[N], new_g[N];
int p[N];
int get(int a) {
return a == p[a] ? a : p[a] = get(p[a]);
}
bool mrg(int a, int b) {
a = get(a);
b = get(b);
if (a == b) {
return false;
}
p[b] = a;
return true;
}
void dfs(int v, int j) {
tin[v] = fup[v] = T++;
used[v] = true;
for (auto [to, i]: g[v]) {
if (i != j) {
if (used[to]) {
ckmn(fup[v], tin[to]);
} else {
dfs(to, i);
ckmn(fup[v], fup[to]);
if (fup[to] > tin[v]) {
bridge[i] = true;
}
}
}
}
}
string ans;
void paint(int v) {
used[v] = true;
color[v] = T;
for (auto [to, i]: g[v]) {
if (!bridge[i] && !used[to]) {
paint(to);
}
}
}
void zhfs(int v) {
assert(!used[v]);
used[v] = true;
if (depth[jump[jump[parent[v]]]] - depth[jump[parent[v]]] == depth[jump[parent[v]]] - depth[parent[v]]) {
jump[v] = jump[jump[parent[v]]];
} else {
jump[v] = parent[v];
}
// assert(v != jump[v]);
for (auto [to, i]: new_g[v]) {
if (to != parent[v]) {
depth[to] = depth[v] + 1;
parent[to] = v;
idx_par[to] = i;
zhfs(to);
}
}
}
int lca(int a, int b) {
if (depth[a] < depth[b]) {
swap(a, b);
}
while (depth[a] > depth[b]) {
if (depth[jump[a]] >= depth[b]) {
a = jump[a];
} else {
a = parent[a];
}
}
while (a != b) {
if (jump[a] != jump[b]) {
a = jump[a];
b = jump[b];
} else {
a = parent[a];
b = parent[b];
}
}
return a;
}
void union_path(int a, int c, int tp) {
a = get(a);
while (a != get(c)) {
assert(mrg(parent[a], a));
assert(idx_par[a] != -1);
if (A[idx_par[a]] == a) {
if (tp == 0) {
ans[idx_par[a]] = 'R';
} else {
ans[idx_par[a]] = 'L';
}
} else {
if (tp == 1) {
ans[idx_par[a]] = 'R';
} else {
ans[idx_par[a]] = 'L';
}
}
a = get(a);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> A[i] >> B[i];
--A[i], --B[i];
g[A[i]].emplace_back(B[i], i);
g[B[i]].emplace_back(A[i], i);
}
cin >> k;
for (int i = 0; i < k; ++i) {
cin >> X[i] >> Y[i];
--X[i], --Y[i];
}
for (int i = 0; i < n; ++i) {
if (!used[i]) {
dfs(i, -1);
}
}
memset(used, 0, sizeof(used));
memset(idx_par, -1, sizeof(idx_par));
T = 0;
for (int i = 0; i < n; ++i) {
if (!used[i]) {
paint(i);
++T;
}
}
for (int i = 0; i < m; ++i) {
if (bridge[i]) {
new_g[color[A[i]]].emplace_back(color[B[i]], i);
new_g[color[B[i]]].emplace_back(color[A[i]], i);
}
}
memset(used, 0, sizeof(used));
for (int i = 0; i < T; ++i) {
if (!used[i]) {
parent[i] = jump[i] = i;
zhfs(i);
}
}
iota(p, p + T, 0);
ans = string(m, 'B');
for (int i = 0; i < k; ++i) {
int a = color[X[i]];
int b = color[Y[i]];
int c = lca(a, b);
union_path(a, c, 0);
union_path(b, c, 1);
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
