#include <bits/stdc++.h>
using namespace std;
/** 1-indexed LCA class */
class least_common_ancestor {
private:
int n, max_log, dfs_cnt = 1;
vector< vector< pair<int, int> > > g;
vector< vector<int> > up;
vector<int> d, dfs_in, dfs_out;
void dfs(int u, int p) {
dfs_in[u] = dfs_cnt++;
up[u][0] = p;
for (int i = 1; i <= max_log; i++) up[u][i] = up[up[u][i - 1]][i - 1];
for (auto &v : g[u]) {
if (v.first == u) continue;
d[v.first] = d[u] + v.second;
dfs(v.first, u);
}
dfs_out[u] = dfs_cnt;
}
void init() {
n = (int) g.size() - 1;
max_log = ceil(log2(n + 1));
up.assign(n + 1, vector<int>(max_log + 1));
d.assign(n + 1, 0);
dfs_in.resize(n + 1);
dfs_out.resize(n + 1);
for (int i = 1; i <= n; i++) if (dfs_in[i] == 0) dfs(i, i);
}
public:
/** Assumes g is an undirected tree. Can be directed if edges point away from vertex the root */
least_common_ancestor(const vector< vector< pair<int, int> > > &_g) : g(_g) {
init();
}
/** Assigns weight 1 to all edges in an unweighted tree */
least_common_ancestor(const vector< vector<int> > &_g) {
g.assign((int) _g.size(), vector< pair<int, int> >());
for (int i = 0; i < (int) _g.size(); i++) {
for (auto &x : _g[i]) g[i].emplace_back(x, 1);
}
init();
}
bool is_anc(int u, int v) {
return dfs_in[u] <= dfs_in[v] && dfs_out[v] <= dfs_out[u];
}
int query(int u, int v) {
if (is_anc(u, v)) return u;
if (is_anc(v, u)) return v;
for (int i = max_log; i >= 0; i--) {
if (!is_anc(up[u][i], v)) u = up[u][i];
}
return up[u][0];
}
int depth(int u) {
return d[u];
}
int dist(int u, int v) {
return d[u] + d[v] - 2 * d[query(u, v)];
}
int preorder(int u) {
return dfs_in[u];
}
int postorder(int u) {
return dfs_out[u];
}
};
vector< vector< pair<int, int> > > g, back, dfs_tree;
vector<bool> was, used;
vector< pair<int, int> > edges, p;
vector<int> up, down, over;
string ans;
void dfs(int u) {
was[u] = true;
for (auto &v : g[u]) {
if (!was[v.first]) {
p[v.first] = {u, v.second};
dfs(v.first);
} else if (v.first != p[u].first && !used[v.second]) {
back[u].push_back(v);
back[v.first].push_back({-u, v.second});
}
used[v.second] = true;
}
}
void dfs_2(int u) {
for (auto &v : dfs_tree[u]) {
dfs_2(v.first);
down[u] += down[v.first];
up[u] += up[v.first];
over[u] += over[v.first];
}
for (auto &v : back[u]) {
if (v.first < 0) over[u]--;
else over[u]++;
}
if (over[u] == 0) {
//assert(down[u] == 0 || up[u] == 0);
if (down[u] > 0) {
if (edges[p[u].second].second == u) ans[p[u].second] = 'R';
else ans[p[u].second] = 'L';
} else {
if (edges[p[u].second].first == u) ans[p[u].second] = 'R';
else ans[p[u].second] = 'L';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
g.resize(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
edges.push_back({u, v});
g[u].push_back({v, i});
g[v].push_back({u, i});
}
was.assign(n + 1, false);
p.assign(n + 1, {-1, -1});
back.resize(n + 1);
used.assign(m, false);
for (int i = 1; i <= n; i++) if (!was[i]) dfs(i);
dfs_tree.resize(n + 1);
for (int i = 2; i <= n; i++) if (p[i].first != -1) dfs_tree[p[i].first].push_back({i, p[i].second});
least_common_ancestor lca(dfs_tree);
up.assign(n + 1, 0); down.assign(n + 1, 0);
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int x, y;
cin >> x >> y;
up[x]++; down[y]++;
int tmp = lca.query(x, y);
up[tmp]--; down[tmp]--;
}
ans = string(m, 'B');
over.assign(n + 1, 0);
dfs_2(1);
for (int i = 0; i < m; i++) cout << ans[i];
cout << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
