#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
const int N = 1e5 + 11;
int n, m;
char ans[N];
vector<int> adj[N];
map<ii, int> dir, org, cnt;
int height[N], lca[N][21];
int top = 0;
int cur[N], low[N];
map<ii, bool> is_bridge;
void dfs(int u, int p = 0) {
cur[u] = low[u] = ++top;
for (int v : adj[u]) {
if (!cur[v]) {
dfs(v, u);
low[u] = min(low[u], low[v]);
// cerr << u << ' ' << v << ' ' << low[v] << ' ' << cur[u] << '\n';
if (low[v] > cur[u]) {
is_bridge[ii(u, v)] = is_bridge[ii(v, u)] = (cnt[ii(u, v)] == 1);
cerr << u << ' ' << v << ' ' << is_bridge[ii(u, v)] << '\n';
}
} else if (v != p)
low[u] = min(low[u], cur[v]);
}
}
int id[N];
ii upd[N];
iii par[N];
vector<iii> adj_compress[N];
void compress(int u) {
id[u] = top;
for (int v : adj[u]) {
if (id[v]) {
if (id[v] != top) {
adj_compress[id[u]].emplace_back(id[v], u, v);
adj_compress[id[v]].emplace_back(id[u], v, u);
}
continue;
}
if (is_bridge[ii(u, v)]) continue;
compress(v);
}
}
void dfs2(int u, int p = -1) {
cur[u] = true;
for (int j = 1; j <= 20; j++)
lca[u][j] = lca[lca[u][j - 1]][j - 1];
for (auto [v, x, y] : adj_compress[u]) {
if (v == p) continue;
height[v] = height[u] + 1;
lca[v][0] = u;
par[v] = iii(u, x, y);
dfs2(v, u);
}
}
void upd_go(int u, int v, int edge_id) {
if (dir[ii(u, v)]) ans[edge_id] = 'R';
else ans[edge_id] = 'L';
}
int cal_lca(int u, int v) {
if (height[u] > height[v]) swap(u, v);
for (int j = 20; j >= 0; j--)
if (height[lca[v][j]] >= height[u])
v = lca[v][j];
if (u == v) return u;
for (int j = 20; j >= 0; j--)
if (lca[u][j] != lca[v][j]) {
u = lca[u][j];
v = lca[v][j];
}
return lca[u][0];
}
int main(int argc, char** argv) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
dir[ii(u, v)] = true;
cnt[ii(u, v)]++; cnt[ii(v, u)]++;
org[ii(u, v)] = org[ii(v, u)] = i;
}
for (int i = 1; i <= n; i++)
if (!cur[i])
dfs(i);
cerr << "--------------------------------" << '\n';
top = 0;
for (int i = 1; i <= n; i++)
if (!id[i]) {
++top;
compress(i);
}
for (int i = 1; i <= top; i++) cur[i] = 0;
for (int i = 1; i <= top; i++)
if (!cur[i]) {
height[i] = 1;
dfs2(i);
}
cerr << "--------------------------------" << '\n';
for (int i = 1; i <= top; i++) upd[i] = ii(1e9, 0);
int q; cin >> q;
while (q--) {
int u, v; cin >> u >> v;
u = id[u], v = id[v];
int p = cal_lca(u, v);
cerr << u << ' ' << v << ' ' << p << '\n';
upd[u] = min(upd[u], ii(height[p], 0));
upd[v] = min(upd[v], ii(height[p], 1));
}
cerr << "--------------------------------" << '\n';
vector<ii> ord;
for (int i = 1; i <= top; i++)
ord.emplace_back(height[i], i);
for (int i = 1; i <= m; i++)
ans[i] = 'B';
sort(ord.begin(), ord.end());
for (auto [_, u] : ord) {
if (upd[u].first >= height[u]) continue;
auto [cur_h, type] = upd[u];
auto [p, x, y] = par[u];
upd[p] = min(upd[p], upd[u]);
int edge_id = org[ii(x, y)];
cerr << x << ' ' << y << ' ' << edge_id << ' ' << type << '\n';
if (!type) upd_go(y, x, edge_id);
else upd_go(x, y, edge_id);
}
for (int i = 1; i <= m; i++)
cout << ans[i];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
