// _| _|
// _| _| _| _| _|_| _|_|_| _|_|_| _| _| _|_| _|_|
// _|_| _| _| _|_|_|_| _| _| _|_| _|_| _|_|_|_| _|_|_|_|
// _| _| _| _| _| _| _| _|_| _| _| _| _|
// _| _| _|_|_| _|_|_| _|_|_| _|_|_| _| _| _|_|_| _|_|_|
// _| _|
// _|_| _|
#include <iostream>
#include <vector>
#include <numeric>
#include <cassert>
using namespace std;
// #define DEBUG
#ifdef DEBUG
#define dassert(x) assert(x);
#define df(...) printf(__VA_ARGS__)
#else
#define dassert(x)
#define df(...)
#endif
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define ir(x, a, b) ((a) <= (x) && (x) <= (b))
#define vec vector
#define sz(x) (ll)x.size()
#define foru(i, n) for (int i = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()
typedef int64_t ll;
int read() {
int n = 0; bool b = 0; char c = getchar();
for (; !ir(c, '0', '9'); c = getchar()) b = (c == '-');
for (; ir(c, '0', '9'); c = getchar()) n = 10*n + (c-'0');
if (b) return -n;
return n;
}
vec<char> used;
vec<vec<pair<int, int>>> g;
vec<int> tin;
vec<int> low;
vec<char> set;
vec<int> which;
vec<int> depth;
vec<int> ans;
vec<int> skip;
vec<pair<int, int>> parent;
vec<int> euleridx;
int lca[int(2e5+100)][40];
int _t = 0;
void lowdfs(int v, int p) {
used[v] = 1;
tin[v] = _t++;
low[v] = tin[v];
bool dup = 0;
for (auto [c, _] : g[v]) {
if (c == p && !dup) {
dup = 1;
continue;
}
if (used[c]) {
df("back edge %d-%d\n", v, c);
low[v] = min(low[v], tin[c]);
} else {
lowdfs(c, v);
low[v] = min(low[v], low[c]);
}
}
}
int compidx = -1;
vec<int> euler;
void compdfs(int v, int p, int idx, bool n) {
if (n) {
euleridx[idx] = euler.size();
euler.pb(idx);
}
which[v] = idx;
used[v] = 1;
df("%d [%d]\n", v, idx);
for (auto [c, i] : g[v]) {
if (used[c] || c == p) continue;
if (tin[c] == low[c]) {
df("bridge %d->%d\n", v, c);
int nidx = ++compidx;
depth[nidx] = depth[idx]+1;
parent[nidx] = {idx, -i};
compdfs(c, v, nidx, 1);
euler.pb(idx);
} else {
compdfs(c, v, idx, 0);
}
}
}
void calclca() {
int n = euler.size();
for (int i = 0; i < n; ++i) {
lca[0][i] = euler[i];
}
for (int k = 1; (1 << k) <= n; ++k) {
for (int i = 0; i + (1 << k) <= n; ++i) {
lca[k][i] = lca[k-1][i + (1 << (k-1))];
if (depth[lca[k-1][i]] < depth[lca[k][i]]) {
lca[k][i] = lca[k-1][i];
}
}
}
}
int log2(int x) {
return 31 - __builtin_clz(x);
}
int getlca(int x, int y) {
x = euleridx[x], y = euleridx[y];
if (y < x) swap(x, y);
int len = y-x+1, k = log2(len), alen = (1 << k);
int ans = lca[k][y - alen + 1];
if (depth[lca[k][x]] < depth[ans]) ans = lca[k][x];
return ans;
}
void setroad(int v, int anc, int set) {
df("going %d {%d}\n", v, depth[v]);
while (depth[v] > depth[anc]) {
int go = skip[v];
if (go == -1) {
int i = parent[v].y;
go = parent[v].x;
skip[v] = anc;
if (i < 0) {
ans[-i] = -set;
} else {
ans[i] = set;
}
} else {
if (depth[anc] < depth[skip[v]]) {
skip[v] = anc;
}
}
df("%d-->%d\n", v, go);
v = go;
}
}
int main() {
df("debug mode\n");
#ifndef DEBUG
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
int n, m;
cin >> n >> m;
g.resize(n);
which.resize(n);
tin.resize(n);
used.resize(n);
low.resize(n);
euleridx.resize(n);
skip.resize(n, -1);
parent.resize(n);
ans.resize(m+1);
depth.resize(n);
foru (i, 20) {
assert(log2(1 << i) == i);
}
foru (i, m) {
int a, b;
cin >> a >> b;
--a, --b;
g[a].pb({b, i+1});
g[b].pb({a, -(i+1)});
}
for (int i = 0; i < n; ++i) {
if (!used[i]) lowdfs(i, i);
}
used.assign(n, 0);
for (int i = 0; i < n; ++i) {
if (!used[i]) {
compdfs(i, i, ++compidx, 1);
}
}
calclca();
df("euler: ");
for (auto x : euler) df("%d ", x);
df("\n");
df("euleridx: ");
for (auto x : euleridx) df("%d ", x);
df("\n");
int p;
cin >> p;
foru (i, p) {
int a, b;
cin >> a >> b;
a = which[a-1], b = which[b-1];
int l = getlca(a, b);
df("going %d to %d [lca: %d]\n", a, b, l);
setroad(a, l, 1);
setroad(b, l, -1);
}
for (int i = 1; i <= m; ++i) {
if (ans[i] == 0) {
cout << 'B';
} else if (ans[i] == -1) {
cout << 'L';
} else {
cout << 'R';
}
}
cout << "\n";
return 0;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:24:11: warning: unused variable 'first' [-Wunused-variable]
24 | #define x first
| ^~~~~
oneway.cpp:201:15: note: in expansion of macro 'x'
201 | for (auto x : euler) df("%d ", x);
| ^
oneway.cpp:24:11: warning: unused variable 'first' [-Wunused-variable]
24 | #define x first
| ^~~~~
oneway.cpp:204:15: note: in expansion of macro 'x'
204 | for (auto x : euleridx) df("%d ", x);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
