#include <bits/stdc++.h>
using namespace std;
#define f1r(i, a, b) for (int i = a; i < b; i++)
#define f0r(i, a) f1r(i, 0, a)
#define trav(t, a) for (auto& t : a)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
template <class T> struct SparseTable {
std::vector<T> v;
std::vector<std::vector<int>> jump;
int level(int x) {
return 31 - __builtin_clz(x);
}
int comb(int a, int b) {
return v[a] == v[b] ? std::min(a, b) : (v[a] < v[b] ? a : b);
}
void init(const std::vector<T>& _v) {
v = _v;
jump = {std::vector<int>((int) v.size())};
iota(jump[0].begin(), jump[0].end(), 0);
for (int j = 1; (1 << j) <= (int) v.size(); j++) {
jump.push_back(std::vector<int>((int) v.size() - (1 << j) + 1));
for (int i = 0; i < (int) jump[j].size(); i++) {
jump[j][i] = comb(jump[j - 1][i], jump[j - 1][i + (1 << (j - 1))]);
}
}
}
int index(int l, int r) {
assert(l <= r);
int d = level(r - l + 1);
return comb(jump[d][l], jump[d][r - (1 << d) + 1]);
}
T query(int l, int r) {
return v[index(l, r)];
}
};
struct LCAJump {
int n;
std::vector<std::vector<int>> par;
std::vector<std::vector<int>> adj;
std::vector<int> depth;
void init(int _n) {
n = _n;
int d = 1;
while ((1 << d) < n) d++;
par.assign(d, std::vector<int>(n));
adj.resize(n);
depth.resize(n);
}
void ae(int x, int y) {
adj[x].push_back(y);
adj[y].push_back(x);
}
void gen(int root = 0) {
par[0][root] = root;
dfs(root);
}
void dfs(int src = 0) {
for (int i = 1; i < (int) par.size(); i++) {
par[i][src] = par[i - 1][par[i - 1][src]];
}
for (int nxt: adj[src]) {
if (nxt == par[0][src]) continue;
depth[nxt] = depth[par[0][nxt] = src] + 1;
dfs(nxt);
}
}
int jump(int x, int d) {
for (int i = 0; i < (int) par.size(); i++) {
if ((d >> i) & 1) {
x = par[i][x];
}
}
return x;
}
int lca(int x, int y) {
if (depth[x] < depth[y]) std::swap(x, y);
x = jump(x, depth[x] - depth[y]);
if (x == y) return x;
for (int i = (int) par.size() - 1; i >= 0; i--) {
int nx = par[i][x];
int ny = par[i][y];
if (nx != ny) x = nx, y = ny;
}
return par[0][x];
}
};
template <class T> struct LazySeg {
std::vector<T> sum, lazy;
int sz;
void init(int sz_) {
sz = 1;
while (sz < sz_) sz *= 2;
sum.assign(2 * sz, 0);
lazy.assign(2 * sz, 0);
}
void push(int ind, int L, int R) {
sum[ind] += (R - L + 1) * lazy[ind];
if (L != R) {
lazy[2 * ind] += lazy[ind];
lazy[2 * ind + 1] += lazy[ind];
}
lazy[ind] = 0;
}
void pull(int ind) {
sum[ind] = sum[2 * ind] + sum[2 * ind + 1];
}
void build() {
for (int i = sz - 1; i >= 1; i--) {
pull(i);
}
}
void upd(int lo, int hi, T inc, int ind = 1, int L = 0, int R = -1) {
if (R == -1) R += sz;
push(ind, L, R);
if (hi < L || R < lo) return ;
if (lo <= L && R <= hi) {
lazy[ind] = inc;
push(ind, L, R);
return;
}
int M = (L + R) / 2;
upd(lo, hi, inc, 2 * ind, L, M);
upd(lo, hi, inc, 2 * ind + 1, M + 1, R);
pull(ind);
}
T qsum(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
if (R == -1) R += sz;
push(ind, L, R);
if (lo > R || L > hi) return 0;
if (lo <= L && R <= hi) return sum[ind];
int M = (L + R) / 2;
return qsum(lo, hi, 2 * ind, L, M) + qsum(lo, hi, 2 * ind + 1, M + 1, R);
}
};
const bool VALUES_IN_VERTICES = false;
template <class T> class HeavyLight {
std::vector<int> parent, heavy, depth, root, tree_pos;
LazySeg<T> tree;
template <class G> int dfs(const G& graph, int v) {
int size = 1, max_subtree = 0;
for (int u : graph[v]) if (u != parent[v]) {
parent[u] = v;
depth[u] = depth[v] + 1;
int subtree = dfs(graph, u);
if (subtree > max_subtree) heavy[v] = u, max_subtree = subtree;
size += subtree;
}
return size;
}
template <class B> void process_path(int u, int v, B op) {
for (; root[u] != root[v]; v = parent[root[v]]) {
if (depth[root[u]] > depth[root[v]]) std::swap(u, v);
op(tree_pos[root[v]], tree_pos[v]);
}
if (depth[u] > depth[v]) std::swap(u, v);
op(tree_pos[u] + (VALUES_IN_VERTICES ? 0 : 1), tree_pos[v]);
}
public:
template <class G>
void init(const G& graph, vi& roots) {
int n = (int) graph.size();
heavy.assign(n, -1);
parent.assign(n, 0);
depth.assign(n, 0);
root.assign(n, 0);
tree_pos.assign(n, 0);
tree.init(n);
trav(r, roots) {
parent[r] = -1;
depth[r] = 0;
dfs(graph, r);
}
for (int i = 0, current_pos = 0; i < n; ++i)
if (parent[i] == -1 || heavy[parent[i]] != i)
for (int j = i; j != -1; j = heavy[j]) {
root[j] = i;
tree_pos[j] = current_pos++;
}
}
void modify_path(int u, int v, const T& value) {
process_path(u, v, [this, &value](int l, int r) { tree.upd(l, r, value); });
}
T query_path(int u, int v) {
T res = 0;
process_path(u, v, [this, &res](int l, int r) { res += tree.qsum(l, r); });
return res;
}
};
struct BCC {
int n, time, num_comps;
std::vector<int> ord, low, id;
// order encountered, earliest time in subtree, component id
std::vector<std::vector<int>> adj, comps, tree;
// adj, comps storage, bridge block tree
std::vector<std::pair<int, int>> bridge;
// bridges
void init(int n_) {
num_comps = time = 0;
n = n_;
ord.assign(n, -1);
low.assign(n, 0);
id.assign(n, -1);
adj.assign(n, std::vector<int>());
comps.clear();
tree.clear();
}
void ae(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
bool is_bridge(int u, int v) {
if (ord[u] > ord[v])
std::swap(u, v);
return ord[u] < low[v];
}
void dfs(int src, int par) {
ord[src] = low[src] = time++;
bool bic = false; // accounts for double edges
for (int nxt : adj[src]) {
if (nxt == par && !bic) {
bic = true;
continue;
}
if (ord[nxt] != -1) {
low[src] = std::min(low[src], ord[nxt]);
continue;
}
dfs(nxt, src);
low[src] = std::min(low[src], low[nxt]);
if (is_bridge(src, nxt))
bridge.emplace_back(src, nxt);
}
}
void fill_component(int src) {
comps[id[src]].push_back(src);
for (int nxt : adj[src]) {
if (id[nxt] != -1 || is_bridge(nxt, src))
continue;
id[nxt] = id[src];
fill_component(nxt);
}
}
void add_component(int src) {
if (id[src] != -1)
return;
id[src] = num_comps++;
comps.emplace_back();
fill_component(src);
}
int build() {
for (int i = 0; i < n; i++)
if (ord[i] == -1)
dfs(i, -1);
for (int i = 0; i < n; i++)
add_component(i);
tree.resize(num_comps);
for (auto& b : bridge) {
int u = id[b.first];
int v = id[b.second];
tree[u].push_back(v);
tree[v].push_back(u);
}
return num_comps;
}
};
int n, m, sz;
HeavyLight<int> H;
BCC B;
LCAJump L;
map<pi, int> conv;
pi cp(int u, int v) {
if (u > v) swap(u, v);
return {u, v};
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
B.init(n);
vi ans(m, -1); // -1 is both
vector<array<int, 3>> ed;
f0r(i, m) {
int u, v; cin >> u >> v;
u--, v--;
B.ae(u, v);
ed.pb({u, v, i});
}
B.build();
trav(e, ed) {
if (B.id[e[0]] != B.id[e[1]]) {
int u = B.id[e[0]];
int v = B.id[e[1]];
conv[mp(u, v)] = e[2];
}
}
vpi tree;
vi vis(sz(B.tree));
function<void(int, int)> dfs = [&](int src, int par) {
if (par != -1) {
tree.eb(src, par);
}
vis[src] = 1;
trav(nxt, B.tree[src]) {
if (nxt == par) continue;
dfs(nxt, src);
}
};
vi roots;
f0r(i, sz(B.tree))
if (!vis[i])
dfs(i, -1), roots.pb(i);
H.init(B.tree, roots);
L.init(sz(B.tree));
trav(e, tree) {
L.ae(e.f, e.s);
}
trav(r, roots) L.gen(r);
int p; cin >> p;
f0r(i, p) {
int x, y; cin >> x >> y;
// all things from x to y are directed
x--, y--;
int u = B.id[x];
int v = B.id[y];
if (u != v) {
int lca = L.lca(u, v);
assert(lca < sz(B.tree));
H.modify_path(u, lca, 1);
H.modify_path(v, lca, -1);
}
}
trav(e, tree) {
int u = e.f;
int p = e.s;
int val = H.query_path(u, p);
int l = -1;
int r = -1;
if (val > 0) {
l = u;
r = p;
} else if (val < 0) {
l = p;
r = u;
}
if (l != -1) {
if (conv.find({l, r}) != conv.end()) {
ans[conv[{l, r}]] = 1;
} else {
ans[conv[{r, l}]] = 0;
}
}
}
f0r(i, m) {
if (ans[i] == -1) {
cout << "B";
} else if (ans[i] == 1) {
cout << "R";
} else {
cout << "L";
}
}
cout << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
496 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
748 KB |
Output is correct |
| 5 |
Correct |
3 ms |
748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
3 ms |
748 KB |
Output is correct |
| 8 |
Correct |
3 ms |
748 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
496 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
748 KB |
Output is correct |
| 5 |
Correct |
3 ms |
748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
3 ms |
748 KB |
Output is correct |
| 8 |
Correct |
3 ms |
748 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
492 KB |
Output is correct |
| 11 |
Correct |
52 ms |
6944 KB |
Output is correct |
| 12 |
Correct |
70 ms |
8352 KB |
Output is correct |
| 13 |
Correct |
103 ms |
11400 KB |
Output is correct |
| 14 |
Correct |
140 ms |
20400 KB |
Output is correct |
| 15 |
Correct |
207 ms |
24608 KB |
Output is correct |
| 16 |
Correct |
362 ms |
45856 KB |
Output is correct |
| 17 |
Correct |
385 ms |
47732 KB |
Output is correct |
| 18 |
Correct |
430 ms |
45956 KB |
Output is correct |
| 19 |
Correct |
349 ms |
48928 KB |
Output is correct |
| 20 |
Correct |
71 ms |
8648 KB |
Output is correct |
| 21 |
Correct |
57 ms |
8660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
496 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
748 KB |
Output is correct |
| 5 |
Correct |
3 ms |
748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
3 ms |
748 KB |
Output is correct |
| 8 |
Correct |
3 ms |
748 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
492 KB |
Output is correct |
| 11 |
Correct |
52 ms |
6944 KB |
Output is correct |
| 12 |
Correct |
70 ms |
8352 KB |
Output is correct |
| 13 |
Correct |
103 ms |
11400 KB |
Output is correct |
| 14 |
Correct |
140 ms |
20400 KB |
Output is correct |
| 15 |
Correct |
207 ms |
24608 KB |
Output is correct |
| 16 |
Correct |
362 ms |
45856 KB |
Output is correct |
| 17 |
Correct |
385 ms |
47732 KB |
Output is correct |
| 18 |
Correct |
430 ms |
45956 KB |
Output is correct |
| 19 |
Correct |
349 ms |
48928 KB |
Output is correct |
| 20 |
Correct |
71 ms |
8648 KB |
Output is correct |
| 21 |
Correct |
57 ms |
8660 KB |
Output is correct |
| 22 |
Correct |
1008 ms |
48848 KB |
Output is correct |
| 23 |
Correct |
1156 ms |
46960 KB |
Output is correct |
| 24 |
Correct |
1182 ms |
47004 KB |
Output is correct |
| 25 |
Correct |
804 ms |
52380 KB |
Output is correct |
| 26 |
Correct |
861 ms |
48412 KB |
Output is correct |
| 27 |
Correct |
1010 ms |
47020 KB |
Output is correct |
| 28 |
Correct |
37 ms |
4256 KB |
Output is correct |
| 29 |
Correct |
92 ms |
9248 KB |
Output is correct |
| 30 |
Correct |
120 ms |
9504 KB |
Output is correct |
| 31 |
Correct |
76 ms |
10016 KB |
Output is correct |
| 32 |
Correct |
304 ms |
22688 KB |
Output is correct |
