#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
bool mini(auto &x, const auto &y) {
if (y < x) {
x = y;
return 1;
}
return 0;
}
bool maxi(auto &x, const auto &y) {
if (y > x) {
x = y;
return 1;
}
return 0;
}
void run();
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
run();
return 0;
}
const int N = (int) 1e5 + 123;
struct E {
int a, b;
};
int n, m;
E e[N];
vector<pair<int, int>> g[N];
bool vis[N];
int tmr;
int tin[N], fup[N];
bool is_bridge[N];
void dfs(int v, int from_id = -1) {
tin[v] = tmr++;
fup[v] = tin[v];
vis[v] = 1;
for (auto &it : g[v]) {
if (it.second == from_id) {
continue;
}
int u = it.first;
if (vis[u]) {
mini(fup[v], tin[u]);
} else {
dfs(u, it.second);
mini(fup[v], fup[u]);
}
}
for (auto &it : g[v]) {
if (it.second == from_id) {
continue;
}
int u = it.first;
int id = it.second;
if (fup[u] > tin[v]) {
is_bridge[id] = 1;
}
}
}
int comps;
int which[N];
vector<pair<int, int>> adj[N];
char ans[N];
void find_comps(int v) {
vis[v] = 1;
which[v] = comps;
for (auto &it : g[v]) {
int u = it.first;
int id = it.second;
if (is_bridge[id]) {
continue;
}
ans[id] = 'B';
if (vis[u]) {
continue;
}
find_comps(u);
}
}
const int L = 20;
int up[N][L];
int depth[N];
void calc_lca(int v, int f = -1) {
if (f == 1) {
rep(i, 0, L) up[v][i] = v;
} else {
up[v][0] = f;
rep(i, 1, L) up[v][i] = up[up[v][i - 1]][i - 1];
}
vis[v] = 1;
for (auto &it : adj[v]) {
int u = it.first;
if (!vis[u]) {
depth[u] = depth[v] + 1;
calc_lca(u, v);
}
}
}
bool test(int mask, int bit) {
return mask & (1 << bit);
}
int go(int v, int h) {
rep(i, 0, L) if (test(h, i)) v = up[v][i];
return v;
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
u = go(u, depth[u] - depth[v]);
if (u == v) return u;
per(i, L - 1, 0) {
int uu = up[u][i];
int vv = up[v][i];
if (uu != vv) {
u = uu, v = vv;
}
}
return up[u][0];
}
int cnt_up[N], cnt_down[N];
void solve(int v, int fid = -1) {
vis[v] = 1;
for (auto &it : adj[v]) {
int u = it.first;
if (vis[u]) continue;
solve(u, it.second);
maxi(cnt_up[v], cnt_up[u] - 1);
maxi(cnt_down[v], cnt_down[u] - 1);
}
assert(cnt_up[v] == 0 || cnt_down[v] == 0);
if (fid != -1) {
if (cnt_up[v] > 0) {
if (which[e[fid].a] == v) {
ans[fid] = 'R';
} else {
ans[fid] = 'L';
}
} else if (cnt_down[v] > 0) {
if (which[e[fid].a] == v) {
ans[fid] = 'L';
} else {
ans[fid] = 'R';
}
} else {
ans[fid] = 'B';
}
}
}
void run() {
cin >> n >> m;
rep(i, 0, m) {
cin >> e[i].a >> e[i].b;
g[e[i].a].pb({e[i].b, i});
g[e[i].b].pb({e[i].a, i});
}
rep(i, 1, n + 1) {
if (!vis[i]) {
dfs(i);
}
}
memset(vis, 0, sizeof vis);
rep(i, 1, n + 1) {
if (!vis[i]) {
find_comps(i);
comps++;
}
}
memset(vis, 0, sizeof vis);
rep(i, 0, m) {
int u = which[e[i].a];
int v = which[e[i].b];
if (u != v) {
adj[u].pb({v, i});
adj[v].pb({u, i});
}
}
rep(i, 0, comps) {
if (!vis[i]) {
calc_lca(i);
}
}
memset(vis, 0, sizeof vis);
int p;
cin >> p;
while (p--) {
int x, y;
cin >> x >> y;
x = which[x], y = which[y];
if (x == y) {
continue;
}
int w = lca(x, y);
maxi(cnt_up[x], depth[x] - depth[w]);
maxi(cnt_down[y], depth[y] - depth[w]);
}
rep(i, 0, comps) {
if (!vis[i]) {
solve(i);
}
}
rep(i, 0, m) {
cout << ans[i];
}
cout << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
