#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
vector<pair<int, int>> adj[N + 8];
pair<int, int> E1[N + 8], E2[N + 8];
pair<int, int> fixed(int u, int v) {return {min(u, v), max(u, v)};}
map<pair<int, int>, int> F;
void add_edge(int u, int v, int id) {
adj[u].push_back({v, id}); adj[v].push_back({u, id});
++F[fixed(u, v)]; E1[id] = {u, v};
}
struct Disjoint_Set_Union {
vector<int> par, sz;
void init(int n) {
par.assign(n + 8, 0); sz.assign(n + 8, 1);
iota(par.begin(), par.end(), 0);
}
int find(int u) {return (par[u] == u ? u : (par[u] = find(par[u])));}
bool join(int u, int v) {
u = find(u); v = find(v);
if (u == v) return 0;
if (sz[u] < sz[v]) swap(u, v);
par[v] = u; sz[u] += sz[v];
return 1;
}
} DSU;
int tin[N + 8], tout[N + 8], low[N + 8], d[N + 8];
pair<int, int> euler[N * 2 + 8];
pair<int, int> SpT[20][N * 2 + 8];
int dp[N + 8]; bool vis[N + 8];
void build_SpT(int n) {
for (int lg = 0; (1 << lg) <= n; ++lg) for (int i = 1; i + (1 << lg) - 1 <= n; ++i) {
if (!lg) SpT[lg][i] = euler[i];
else SpT[lg][i] = min(SpT[lg - 1][i], SpT[lg - 1][i + (1 << (lg - 1))]);
}
}
pair<int, int> rmq(int l, int r) {
if (l > r) swap(l, r);
int lg = __lg(r - l + 1);
return min(SpT[lg][l], SpT[lg][r - (1 << lg) + 1]);
}
int LCA(int u, int v) {return rmq(tin[u], tin[v]).second;}
struct Solver {
int timer; vector<tuple<int, int, int>> bridges;
vector<pair<int, int>> Tadj[N + 8];
Solver() {}
void init(int n) {timer = 0; DSU.init(n);}
void add_tree_edge(int u, int v, int id) {
Tadj[u].push_back({v, id}); Tadj[v].push_back({u, id});
// cout << u << ' ' << v << ' ' << id << '\n';
}
void DFS_build(int u, int p) {
tin[u] = low[u] = ++timer;
for (auto [v, id] : adj[u]) if (v != p) {
if (tin[v]) low[u] = min(low[u], tin[v]);
else {
DFS_build(v, u); low[u] = min(low[u], low[v]);
if (low[v] > tin[u] && F[fixed(u, v)] == 1) {
bridges.push_back({u, v, id});
// cout << u << " -> " << v << " is a bridge!!\n";
}
else DSU.join(u, v);
}
}
}
void DFS_EulerTour(int u, int p) {
tin[u] = ++timer; euler[timer] = {d[u], u};
for (auto [v, id] : Tadj[u]) if (v != p) {
d[v] = d[u] + 1; DFS_EulerTour(v, u);
euler[++timer] = {d[u], u};
}
tout[u] = timer;
}
void build_tree(int n) {
for (int i = 1; i <= n; ++i) if (!tin[i]) DFS_build(i, i);
for (auto [u, v, id] : bridges) add_tree_edge(DSU.find(u), DSU.find(v), id);
timer = 0;
for (int i = 1; i <= n; ++i) if (!tout[i]) DFS_EulerTour(i, i);
build_SpT(timer);
}
// u -> par[u] : -1; par[u] -> u: 1
int A;
void add_constraint(int u, int v) { // u --> v
u = DSU.find(u); v = DSU.find(v);
A = LCA(u, v);
--dp[u]; ++dp[v];
}
void DFS_sweep(int u, int p) {
vis[u] = 1;
for (auto [v, id] : Tadj[u]) if (v != p) DFS_sweep(v, u), dp[u] += dp[v];
// cout << u << ' ' << dp[u] << '\n';
}
void DFS_label(int u, int p) {
for (auto [v, id] : Tadj[u]) if (v != p) {
DFS_label(v, u);
if (!dp[v]) continue;
else {
E1[id].first = DSU.find(E1[id].first);
E1[id].second = DSU.find(E1[id].second);
if (dp[v] < 0) E2[id] = {v, u};
else E2[id] = {u, v};
}
}
}
void solve(int n) {
for (int i = 1; i <= n; ++i) if (!vis[i]) DFS_sweep(i, i), DFS_label(i, i);
}
} DS;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m, u, v; cin >> n >> m; DS.init(n);
for (int i = 1; i <= m; ++i) cin >> u >> v, add_edge(u, v, i);
DS.build_tree(n);
int q; cin >> q;
while (q--) cin >> u >> v, DS.add_constraint(u, v);
DS.solve(n);
// for (int i = 1; i <= m; ++i) cout << E1[i].first << ' ' << E1[i].second << ' ' << E2[i].first << ' ' << E2[i].second << '\n';
for (int i = 1; i <= m; ++i)
if (!E2[i].first) cout << 'B';
else if (E1[i] == E2[i]) cout << 'L';
else cout << 'R';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
