#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 20
const ll MOD = 1e9 + 7;
const ll MAXN = 1e5 + 100;
vector<vector<int>> graph, G, G2;
int mark[MAXN], a[MAXN], b[MAXN], vis[MAXN], par[MAXN], sz[MAXN], ways[MAXN];
int up[LOGN][MAXN], depth[MAXN];
void dfs(int node, int parent) {
vis[node] = 1;
for (auto u : graph[node]) {
if (u != parent && vis[u] != 2)
G[node].push_back(u);
if (!vis[u])
dfs(u, node);
}
vis[node] = 2;
}
int find(int node) {
if (node == par[node])
return node;
return par[node] = find(par[node]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b)
return ;
if (sz[b] > sz[a])
swap(a, b);
par[b] = a;
sz[a] += sz[b];
}
stack<int> nds;
void dfs2(int node) {
vis[node] = true;
nds.push(node);
for (auto u : G[node]) {
if (vis[u] == 0)
dfs2(u);
}
}
void dfs3(int node) {
vis[node] = true;
for (auto u : G[node]) {
if (vis[u])
continue;
unite(node, u);
dfs3(u);
}
}
void prep(int node, int parent) {
for (auto u : G2[node]) {
if (u != parent) {
up[0][u] = node;
depth[u] = depth[node] + 1;
for (int i = 1; i < LOGN; i++)
up[i][u] = up[i-1][up[i-1][u]];
prep(u, node);
}
}
}
int lift(int node, int k) {
for (int i = 0; i < LOGN; i++) {
if ((1<<i) & k)
node = up[i][node];
}
return node;
}
int lca(int a, int b) {
if (depth[b] > depth[a])
swap(a, b);
a = lift(a, depth[a] - depth[b]);
if (a == b)
return a;
for (int i = LOGN-1; i >= 0; i--) {
if (up[i][a] != up[i][b]) {
a = up[i][a];
b = up[i][b];
}
}
return up[0][a];
}
map<pair<int,int>,int> mp;
void dfs4(int node, int parent) {
for (auto u : G2[node]) {
if (u == parent)
continue;
dfs4(u, node);
mark[node] += mark[u];
if (mark[u] > 0) { // edge : u -> node
if (mp[{u, node}] == 0)
ways[mp[{node, u}]] = 1;
else
ways[mp[{u, node}]] = 2;
} else if (mark[u] < 0) { // edge : node -> u
if (mp[{u, node}] == 0)
ways[mp[{node, u}]] = 2;
else
ways[mp[{u, node}]] = 1;
}
}
}
int main() {
fast
int n, m, q;
cin >> n >> m;
for (int i = 1; i <= n; i++)
par[i] = i, sz[i] = 1;
graph = vector<vector<int>>(n+1, vector<int>());
G = vector<vector<int>>(n+1, vector<int>());
G2 = vector<vector<int>>(n+1, vector<int>());
for (int i = 1; i <= m; i++) {
cin >> a[i] >> b[i];
graph[a[i]].push_back(b[i]);
graph[b[i]].push_back(a[i]);
}
dfs(1, 1);
for (int i = 1; i <= n; i++)
vis[i] = 0;
dfs2(1);
for (int i = 1; i <= n; i++)
vis[i] = 0;
while (nds.size()) {
int node = nds.top();
nds.pop();
if (!vis[node])
dfs3(node);
}
for (int i = 1; i <= m; i++) {
if (find(a[i]) != find(b[i]))
mp[{find(a[i]), find(b[i])}] = i;
}
for (int i = 1; i <= m; i++) {
if (find(a[i]) == find(b[i]))
ways[i] = -1;
else {
G2[find(a[i])].push_back(find(b[i]));
G2[find(b[i])].push_back(find(a[i]));
}
}
for (int i = 0; i < LOGN; i++)
up[i][find(1)] = find(1);
prep(find(1), find(1));
cin >> q;
while (q--) {
int a, b;
cin >> a >> b;
a = find(a);
b = find(b);
if (a == b)
continue;
int LCA = lca(a, b);
if (LCA != a && LCA != b) {
mark[a] += 1;
mark[b] -= 1;
} else if (LCA == a) {
mark[b] += 1;
mark[a] -= 1;
} else if (LCA == b) {
mark[a] += 1;
mark[b] -= 1;
}
}
dfs4(find(1), find(1));
for (int i = 1; i <= m; i++) {
if (ways[i] == -1)
cout << "B";
else if (ways[i] == 1)
cout << "L";
else if (ways[i] == 2)
cout << "R";
else
cout << "B";
}
cout << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
