/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 100000;
const int BITS = 18;
int n, m;
int eu[N_MAX + 2], ev[N_MAX + 2];
vector <int> adj[N_MAX + 2];
multiset <pair <int, int>> es;
bool seen[N_MAX + 2];
int parent[N_MAX + 2];
int level[N_MAX + 2];
int minAbove[N_MAX + 2];
bool bridge[N_MAX + 2];
void dfs (int u) {
seen[u] = true;
minAbove[u] = level[u];
for (int v : adj[u]) {
if (seen[v] == false) {
parent[v] = u;
level[v] = level[u] + 1;
dfs(v);
minAbove[u] = min(minAbove[u], minAbove[v]);
} else if (v != parent[u] || es.count(make_pair(u, v)) > 1) {
minAbove[u] = min(minAbove[u], level[v]);
}
}
if (minAbove[u] >= level[u]) {
bridge[u] = true;
}
}
int DSU[N_MAX + 2];
void DSUinit () {
for (int u = 1; u <= n; u++) {
DSU[u] = u;
}
}
int DSUroot (int u) {
return (DSU[u] == u ? u : DSU[u] = DSUroot(DSU[u]));
}
void DSUjoin (int u, int v) {
DSU[DSUroot(u)] = DSUroot(v);
}
vector <int> tree[N_MAX + 2];
int treeParent[N_MAX + 2];
int depth[N_MAX + 2];
void treeDfs (int u) {
seen[u] = true;
for (int v : tree[u]) {
if (v != treeParent[u]) {
treeParent[v] = u;
depth[v] = depth[u] + 1;
treeDfs(v);
}
}
}
int anc[N_MAX + 2][BITS];
int ancestor (int u, int len) {
seen[u] = true;
for (int b = BITS - 1; b >= 0; b--) {
if ((1 << b) <= len) {
u = anc[u][b];
len -= (1 << b);
}
}
return u;
}
int lca (int u, int v) {
if (depth[u] > depth[v]) {
u = ancestor(u, depth[u] - depth[v]);
} else if (depth[v] > depth[u]) {
v = ancestor(v, depth[v] - depth[u]);
}
if (u == v) {
return u;
}
for (int b = BITS - 1; b >= 0; b--) {
if (anc[u][b] != anc[v][b]) {
u = anc[u][b];
v = anc[v][b];
}
}
return treeParent[u];
}
int k;
int up[N_MAX + 2];
int down[N_MAX + 2];
int type[N_MAX + 2];
void propagate (int u) {
for (int v : tree[u]) {
if (v != treeParent[u]) {
propagate(v);
up[u] += up[v];
down[u] += down[v];
}
}
if (up[u] > 0) {
type[u] = 1;
} else if (down[u] > 0) {
type[u] = 2;
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> eu[i] >> ev[i];
if (eu[i] != ev[i]) {
adj[eu[i]].push_back(ev[i]);
adj[ev[i]].push_back(eu[i]);
es.insert(make_pair(eu[i], ev[i]));
es.insert(make_pair(ev[i], eu[i]));
}
}
for (int u = 1; u <= n; u++) {
if (seen[u] == false) {
dfs(u);
}
}
DSUinit();
for (int u = 1; u <= n; u++) {
if (parent[u] != 0 && bridge[u] == false) {
DSUjoin(u, parent[u]);
}
}
for (int u = 1; u <= n; u++) {
if (parent[u] != 0 && bridge[u] == true) {
int x = DSUroot(u), y = DSUroot(parent[u]);
tree[x].push_back(y);
tree[y].push_back(x);
}
}
fill(seen + 1, seen + n + 1, false);
for (int u = 1; u <= n; u++) {
if (DSU[u] == u && seen[u] == false) {
treeDfs(u);
}
}
for (int u = 1; u <= n; u++) {
anc[u][0] = treeParent[u];
}
for (int b = 1; b < BITS; b++) {
for (int u = 1; u <= n; u++) {
anc[u][b] = anc[anc[u][b - 1]][b - 1];
}
}
cin >> k;
for (int i = 1; i <= k; i++) {
int u, v;
cin >> u >> v;
int x = DSUroot(u), y = DSUroot(v);
int z = lca(x, y);
up[x]++; up[z]--;
down[y]++; down[z]--;
}
fill(seen + 1, seen + n + 1, false);
for (int u = 1; u <= n; u++) {
if (DSU[u] == u && seen[u] == false) {
propagate(u);
}
}
for (int i = 1; i <= m; i++) {
int x = DSUroot(eu[i]), y = DSUroot(ev[i]);
if (x == y) {
cout << 'B';
} else if (y == treeParent[x]) {
if (type[x] == 0) {
cout << 'B';
} else {
cout << (type[x] == 1 ? 'R' : 'L');
}
} else {
assert(x == treeParent[y]);
if (type[y] == 0) {
cout << 'B';
} else {
cout << (type[y] == 1 ? 'L' : 'R');
}
}
}
cout << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
