#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int lg = 18;
#define fi first
#define se second
vector<pair<int, int>> adj[N];
pair<int, int> edges[N];
set<int> b;
vector<char> ans(N, 'B');
int n, m, pairs, low[N], st[N], timer = 0, k = 0, bcc[N], road_id = 0, lift[N][lg], dep[N], pa[N];
pair<int, int> up[N], down[N];
struct edge {
int v, id;
char dir;
};
vector<edge> g[N];
void dfs(int u, int p) {
low[u] = st[u] = ++timer;
for (auto& [v, id] : adj[u]) {
if (!st[v]) {
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > st[u]) b.insert(id);
} else if (v != p) {
low[u] = min(low[u], st[v]);
}
}
}
void Dfs(int u) {
bcc[u] = k;
for (auto& [v, id] : adj[u]) {
if (b.count(id)) continue;
if (!bcc[v]) Dfs(v);
}
}
void pre(int u) {
for (int i = 1; i < lg; i++) lift[u][i] = lift[lift[u][i - 1]][i - 1];
for (auto& [v, id, dir] : g[u]) {
if (lift[u][0] != v) {
dep[v] = dep[u] + 1;
pa[v] = u;
lift[v][0] = u;
pre(v);
}
}
}
int jump(int sta, int dist) {
for (int i = lg - 1; i >= 0; i--) if (dist & (1 << i)) sta = lift[sta][i];
return sta;
}
int get_lca(int u, int v) {
if (dep[u] > dep[v]) swap(u, v);
v = jump(v, dep[v] - dep[u]);
if (u == v) return u;
for (int i = lg - 1; i >= 0; i--) {
int ut = lift[u][i], vt = lift[v][i];
if (ut != vt) u = ut, v = vt;
}
return lift[u][0];
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
road_id++;
adj[u].push_back({v, road_id});
adj[v].push_back({u, road_id});
edges[road_id] = {u, v};
}
dfs(1, 0);
for (int i = 1; i <= n; i++) {
if (!bcc[i]) {
k++;
Dfs(i);
}
}
for (int i = 1; i <= m; i++) {
int u = bcc[edges[i].fi], v = bcc[edges[i].se];
if (u == v) continue;
g[u].push_back((edge) {v, i, 'R'});
g[v].push_back((edge) {u, i, 'L'});
}
lift[1][0] = 1;
pre(1);
for (int i = 1; i <= m; i++) {
int u = bcc[edges[i].fi], v = bcc[edges[i].se];
if (u == v) continue;
if (dep[u] > dep[v]) up[u] = {i, 'R'};
else up[v] = {i, 'L'};
}
cin >> pairs;
while (pairs--) {
int u, v;
cin >> u >> v;
u = bcc[u], v = bcc[v];
int lca = get_lca(u, v);
while (u != lca) ans[up[u].first] = up[u].second, u = pa[u];
while (v != lca) ans[up[v].first] = (up[v].second == 'R' ? 'L' : 'R'), v = pa[v];
}
for (int i = 1; i <= m; i++) cout << ans[i];
cout << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
