#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m, p;
vector<int> adj[MAXN];
int a[MAXN], b[MAXN];
int x[MAXN], y[MAXN];
int Time;
int dfn[MAXN], low[MAXN];
map<pair<int, int>, bool> bridge;
void dfs(int cur, int p = -1) {
dfn[cur] = low[cur] = ++Time;
for (int v : adj[cur]) if (v != p) {
if (!dfn[v]) {
dfs(v, cur);
low[cur] = min(low[cur], low[v]);
if (low[v] > dfn[cur]) {
bridge[make_pair(cur, v)] = bridge[make_pair(v, cur)] = true;
}
} else if (dfn[v] < dfn[cur]) {
low[cur] = min(low[cur], dfn[v]);
}
}
}
bitset<MAXN> vis;
int n_blocks;
int block[MAXN];
void dfs2(int cur, int p = -1) {
vis[cur] = 1;
if (p != -1) {
block[cur] = block[p];
}
for (int v : adj[cur]) if (v != p) {
if (!vis[v] && !bridge[make_pair(cur, v)]) {
dfs2(v, cur);
}
}
}
set<int> tadj[MAXN];
int pre[MAXN];
map<pair<int, int>, pair<int, int> > inp_ori;
map<pair<int, int>, char> mp;
int dfs3(int cur, int p = -1) {
int val = pre[cur];
for (int v : tadj[cur]) if (v != p) {
val += dfs3(v, cur);
}
pair<int, int> pi = make_pair(p, cur);
bool same = (pi == inp_ori[pi]);
if (val < 0) {
if (same) {
mp[inp_ori[pi]] = 'L';
} else {
mp[inp_ori[pi]] = 'R';
}
} else if (val > 0) {
if (same) {
mp[inp_ori[pi]] = 'R';
} else {
mp[inp_ori[pi]] = 'L';
}
} else {
mp[inp_ori[pi]] = 'B';
}
return val;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> a[i] >> b[i];
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
cin >> p;
for (int i = 1; i <= p; i++) {
cin >> x[i] >> y[i];
}
dfs(1);
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
block[i] = ++n_blocks;
dfs2(i);
}
}
for (int i = 1; i <= m; i++) {
int A = block[a[i]];
int B = block[b[i]];
if (A != B) { // bridge
inp_ori[make_pair(A, B)] = inp_ori[make_pair(B, A)] = make_pair(A, B);
tadj[A].insert(B);
tadj[B].insert(A);
}
}
for (int i = 1; i <= p; i++) {
int u = block[x[i]];
int v = block[y[i]];
if (u == v) {
continue;
}
pre[u]--;
pre[v]++;
}
dfs3(1);
for (int i = 1; i <= m; i++) {
int u = block[a[i]];
int v = block[b[i]];
if (u == v) {
cout << 'B';
} else {
cout << mp[make_pair(u, v)];
}
}
cout << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
7416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
7416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
7416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
