#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 1e5 + 5;
int num[mn], low[mn], sz[mn], depth[mn], timeDfs;
int up[mn][21], st[mn][21], en[mn][21];
bool isBridge[mn], vis[mn];
vector<pii> adj[mn];
void dfs (int u, int preID, int d, int p) {
num[u] = low[u] = ++timeDfs, depth[u] = d;
vis[u] = 1, sz[u] = 1, up[u][0] = p;
for (int i = 1; i < 17; i++)
up[u][i] = up[up[u][i - 1]][i - 1];
for (pii it : adj[u]) {
int v, id; tie(v, id) = it;
if (id == preID) continue;
if (!vis[v]) {
dfs(v, id, d + 1, u);
sz[u] += sz[v], low[u] = min(low[u], low[v]);
if (low[v] == num[v]) isBridge[id] = 1;
}
else low[u] = min(low[u], num[v]);
}
}
int goUp (int a, int k) {
for (int i = 0; i < 17; i++)
if (k & (1 << i)) a = up[a][i];
return a;
}
int lca (int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
a = goUp(a, depth[a] - depth[b]);
if (a == b) return a;
for (int i = 16; i >= 0; i--)
if (up[a][i] != up[b][i])
a = up[a][i], b = up[b][i];
return up[a][0];
}
int queryST (int u) {
int l = num[u], r = num[u] + sz[u] - 1, p = 31 - __builtin_clz(r - l + 1);
return min(st[l][p], st[r - (1 << p) + 1][p]);
}
int queryEN (int u) {
int l = num[u], r = num[u] + sz[u] - 1, p = 31 - __builtin_clz(r - l + 1);
return min(en[l][p], en[r - (1 << p) + 1][p]);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
vector<pii> edge(m);
vector<char> ans(m);
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
if (a != b) {
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
else ans[i] = 'B';
edge[i] = {a, b};
}
dfs(1, -1, 1, 0);
for (int i = 1; i <= n; i++)
for (int j = 0; j < 17; j++)
st[i][j] = en[i][j] = INT_MAX;
int p; cin >> p;
while (p--) {
int a, b; cin >> a >> b;
int lc = lca(a, b); // a -> lca -> b
st[num[a]][0] = min(st[num[a]][0], depth[lca(a, b)]);
en[num[b]][0] = min(en[num[b]][0], depth[lca(a, b)]);
}
for (int s = 1; (1 << s) <= n; s++) {
for (int i = 1; i + (1 << s) - 1 <= n; i++) {
int p = s - 1;
st[i][s] = min(st[i][p], st[i + (1 << p)][p]);
en[i][s] = min(en[i][p], en[i + (1 << p)][p]);
}
}
for (int i = 0; i < m; i++) {
int a, b; bool flp = 0; tie(a, b) = edge[i];
if (depth[a] > depth[b]) {
swap(a, b);
flp = 1;
}
if (!isBridge[i]) ans[i] = 'B';
else {
if (queryST(b) <= depth[a]) ans[i] = (flp ? 'R' : 'L');
else if (queryEN(b) <= depth[a]) ans[i] = (flp ? 'L' : 'R');
else ans[i] = 'B';
}
}
for (int i = 0; i < m; i++) cout << ans[i];
return 0;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:90:13: warning: unused variable 'lc' [-Wunused-variable]
90 | int lc = lca(a, b); // a -> lca -> b
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
