//! The Leader Of Retards Bemola
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define sz(x) (ll) x.size()
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
ll Pow(ll a, ll b, ll md, ll ans = 1) {
for (; b; b >>= 1, a = a * a % md)
if (b & 1)
ans = ans * a % md;
return ans % md;
}
const ll MAXN = 1e5 + 2;
const ll LOG = 19;
const ll MOD = 1e9 + 7;
ll mark[MAXN], par[LOG][MAXN], B[MAXN], P[MAXN], M[MAXN], H[MAXN], ps[2][MAXN], n, m, k;
vector<pll> adj[MAXN]; pll E[MAXN];
void preDFS(ll v, ll p = 0) {
M[v] = MOD; mark[v] = 1;
H[v] = H[p] + 1;
for (pll u : adj[v]) {
if (mark[u.F] == 0) {
preDFS(u.F, v);
M[v] = min(M[v], M[u.F]);
if (M[u.F] > H[v]) B[u.S] = 1;
} else if (u.F != p) {
M[v] = min(M[v], H[u.F]);
}
}
}
void DFS(ll v, ll p = 0) {
H[v] = H[p] + 1; mark[v] = 1;
if (p == -1) par[0][v] = v;
for (ll i = 1; i < LOG; i++) {
par[i][v] = par[i - 1][par[i - 1][v]];
}
for (auto[u, tmp] : adj[v]) {
if (mark[u] == 0) {
par[0][u] = v;
DFS(u, v);
}
}
}
ll getpar(ll v, ll h) {
for (ll i = LOG - 1; i--;) {
if (h & (1 << i)) v = par[i][v];
}
return v;
}
ll LCA(ll u, ll v) {
if (H[u] < H[v]) swap(u, v);
u = getpar(u, H[u] - H[v]);
if (u == v) return v;
for (ll i = LOG - 1; i--;) {
if (par[i][v] != par[i][u]) {
v = par[i][v], u = par[i][u];
}
}
return par[0][v];
}
void calcDFS(ll v, ll p = 0) {
H[v] = H[p] + 1; mark[v] = 1;
for (auto[u, tmp] : adj[v]) {
if (mark[u] == 0) {
calcDFS(u, v);
ps[0][v] += ps[0][u];
ps[1][v] += ps[1][u];
}
}
}
ll Find(ll v) {
return P[v] == -1 ? v : P[v] = Find(P[v]);
}
ll Union(ll u, ll v) {
v = Find(v), u = Find(u);
if (u == v) return 0;
P[u] = v;
return 1;
}
int main() {
fill(P, P + MAXN, -1);
scanf("%d%d", &n, &m);
for (ll i = 1; i <= m; i++) {
ll u, v; scanf("%d%d", &u, &v);
adj[v].push_back({u, i});
adj[u].push_back({v, i}); E[i] = {u, v};
}
for (ll i = 1; i <= n; i++) if (mark[i] == 0) preDFS(i);
memset(H, 0, sizeof H);
memset(mark, 0, sizeof mark);
for (ll i = 1; i <= m; i++) {
if (B[i] == 0) Union(E[i].F, E[i].S);
}
for (ll i = 1; i <= n; i++) adj[i].clear(), adj[i].shrink_to_fit();
for (ll i = 1; i <= m; i++) {
if (B[i]) {
ll u = Find(E[i].F), v = Find(E[i].S);
adj[u].push_back({v, 0});
adj[v].push_back({u, 0});
}
}
for (ll i = 1; i <= n; i++) {
if (i != Find(i) || mark[i]) continue;
DFS(i);
}
scanf("%d", &k);
for (ll i = 1; i <= k; i++) {
ll x, y, l; scanf("%d%d", &x, &y); x = Find(x), y = Find(y);
l = LCA(x, y);
ps[0][x]++, ps[0][l]--;
ps[1][y]++, ps[1][l]--;
}
memset(H, 0, sizeof H);
memset(mark, 0, sizeof mark);
for (ll i = 1; i <= n; i++) {
if (i != Find(i) || mark[i]) continue;
calcDFS(i);
}
for (ll i = 1; i <= m; i++) {
ll u = E[i].F, v = E[i].S, f = 0; u = Find(u), v = Find(v);
if (H[u] < H[v]) swap(u, v), f = 1;
if (ps[0][u] && ps[1][u]) printf("B");
else if (B[i] == 0) printf("B");
else if (ps[0][u] == 0 && ps[1][u] == 0) printf("B");
else if (ps[0][u]) {
if (f) printf("L");
else printf("R");
} else {
if (f) printf("R");
else printf("L");
}
}
printf("\n");
return 0;
}
Compilation message
oneway.cpp: In function 'void DFS(ll, ll)':
oneway.cpp:47:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
47 | for (auto[u, tmp] : adj[v]) {
| ^
oneway.cpp: In function 'void calcDFS(ll, ll)':
oneway.cpp:76:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
76 | for (auto[u, tmp] : adj[v]) {
| ^
oneway.cpp: In function 'int main()':
oneway.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
98 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:100:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
100 | ll u, v; scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
122 | scanf("%d", &k);
| ~~~~~^~~~~~~~~~
oneway.cpp:124:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
124 | ll x, y, l; scanf("%d%d", &x, &y); x = Find(x), y = Find(y);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3948 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
3948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3948 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
3948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3948 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
3948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
