#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct edge {
int v, id;
bool inv;
};
vector<edge> g[100005], tree[100005];
int n, tin[100005], low[100005], dsu[100005], t[100005], p[100005], sz[100005], d[100005], h[100005], k;
bool bridge[100005], vis[100005];
map<pair<int, int>, int> edge;
int find (int u) {
return dsu[u] == u ? u : dsu[u] = find(dsu[u]);
}
void dfs (int u, int f) {
tin[u] = low[u] = ++k;
for (auto& [v, id, inv] : g[u]) if (v != f) {
if (tin[v]) low[u] = min(low[u], tin[v]);
else {
dfs(v, u);
low[u] = min(low[u], low[v]);
}
bridge[id] = tin[u] < low[v] && edge[{u, v}] == 1;
}
}
void dfs (int u) {
vis[u] = true;
for (auto& [v, id, inv] : g[u]) {
if (!bridge[id]) {
int ru = find(u), rv = find(v);
if (ru != rv) dsu[ru] = rv;
}
if (!vis[v]) dfs(v);
}
}
void fsd (int u) {
vis[u] = true;
for (auto& [v, id, inv] : g[u]) {
if (bridge[id]) {
tree[find(u)].push_back({find(v), id, inv});
tree[find(v)].push_back({find(u), id, !inv});
}
if (!vis[v]) fsd(v);
}
}
void sdf (int u, int f) {
p[u] = f;
sz[u] = 1;
if ((int) tree[u].size() > 1 && tree[u][0].v == f) swap(tree[u][0], tree[u][1]);
for (int i = 0; i < (int) tree[u].size(); i++) if (tree[u][i].v != f) {
d[tree[u][i].v] = d[u]+1;
sdf(tree[u][i].v, u);
sz[u] += sz[tree[u][i].v];
if (sz[tree[u][i].v] > sz[tree[u][0].v]) swap(tree[u][0], tree[u][i]);
}
}
void hld (int u, int head) {
t[u] = ++k;
h[u] = head;
if (!tree[u].empty() && tree[u][0].v != p[u]) hld(tree[u][0].v, head);
for (int i = 1; i < (int) tree[u].size(); i++) if (tree[u][i].v != p[u]) hld(tree[u][i].v, tree[u][i].v);
}
struct node {
int sum, lz;
node () {sum = lz = 0;}
} seg[400005];
void push (int id, int len) {
seg[id].sum += seg[id].lz * len;
if (id <= n*2) {
seg[id*2].lz += seg[id].lz;
seg[id*2+1].lz += seg[id].lz;
}
seg[id].lz = 0;
}
void upd (int l, int r, int id, int ql, int qr, int val) {
push(id, r-l+1);
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
seg[id].lz += val;
push(id, r-l+1);
return;
}
upd(l, (l+r)/2, id*2, ql, qr, val);
upd((l+r)/2+1, r, id*2+1, ql, qr, val);
}
int query (int l, int r, int id, int idx) {
push(id, r-l+1);
if (l == r) return seg[id].sum;
int mid = (l+r)/2;
if (mid < idx) return query(mid+1, r, id*2+1, idx);
return query(l, mid, id*2, idx);
}
vector<char> ans;
void dfs_ans (int u, int f) {
vis[u] = true;
int q = query(1, n, 1, t[u]);
if (q) for (auto& [v, id, inv] : tree[u]) if (v == f) ans[id] = ((q > 0) ^ inv) ? 'R' : 'L';
for (auto& [v, id, inv] : tree[u]) if (v != f) dfs_ans(v, u);
}
int main () {
int m;
cin >> n >> m;
ans.resize(m+1);
for (int i = 1; i <= n; i++) dsu[i] = i;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
if (u != v) {
edge[{u, v}]++;
edge[{v, u}]++;
g[u].push_back({v, i+1, 0});
g[v].push_back({u, i+1, 1});
}
}
for (int i = 1; i <= n; i++) if (!tin[i]) dfs(i, 0);
for (int i = 1; i <= n; i++) if (!vis[i]) dfs(i);
for (int i = 1; i <= n; i++) vis[i] = false;
for (int i = 1; i <= n; i++) if (!vis[i]) fsd(i);
k = 0;
for (int i = 1; i <= n; i++) if (!sz[find(i)]) sdf(find(i), 0);
for (int i = 1; i <= n; i++) if (!t[find(i)]) hld(find(i), find(i));
int q;
cin >> q;
while (q--) {
int u, v;
cin >> u >> v;
u = find(u), v = find(v);
int mul = 1;
if (u == v) continue;
while (h[u] != h[v]) {
if (d[h[u]] < d[h[v]]) {
swap(u, v);
mul = -mul;
}
upd(1, n, 1, t[h[u]], t[u], mul);
u = p[h[u]];
}
if (d[u] < d[v]) {
swap(u, v);
mul = -mul;
}
upd(1, n, 1, t[v]+1, t[u], mul);
}
for (int i = 1; i <= n; i++) vis[i] = false;
for (int i = 1; i <= n; i++) if (!vis[find(i)]) dfs_ans(find(i), 0);
for (int i = 1; i <= m; i++) cout << (ans[i] ? ans[i] : 'B');
cout << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
11356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
11356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
11356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
