#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> par, size;
DSU(int n = 0) {
par.resize(n+1, 0);
size.resize(n+1, 0);
for (int i = 1; i <= n; i++) {
par[i] = i;
}
}
int find(int v) {
return par[v] == v ? v : par[v] = find(par[v]);
}
void merge(int a, int b) {
a = find(a), b = find(b);
if (a != b) {
if (size[a] < size[b]) swap(a,b);
par[b] = a;
size[a] += size[b];
}
}
};
const int MAXN = 100000;
vector<int> adj[MAXN+1];
vector<int> comp[MAXN+1];
vector<pair<int,int>> bridges, graph;
map<pair<int,int>,int> ind;
map<pair<int,int>,pair<int,int>> compToOriginal;
DSU d;
int dep[MAXN + 1], low[MAXN + 1], par[17][MAXN + 1], lay[MAXN + 1];
void dfs1(int v, int p) {
dep[v] = low[v] = dep[p] + 1;
for (int u : adj[v]) {
if (u == p) continue;
if (dep[u] == 0) {
dfs1(u, v);
low[v] = min(low[v], low[u]);
} else {
low[v] = min(low[v], dep[u]);
d.merge(v, u);
}
}
if (v == 1) return;
if (low[v] == dep[v]) {
if (binary_search(graph.begin(), graph.end(), make_pair(p,v))) {
bridges.push_back({p,v});
} else {
bridges.push_back({v,p});
}
} else {
d.merge(p, v);
}
}
void dfs2(int v, int p) {
par[0][v] = p;
lay[v] = lay[p] + 1;
for (int k = 1; k < 17; k++) {
par[k][v] = par[k-1][par[k-1][v]];
}
for (auto u : comp[v]) if (u != p) {
dfs2(u, v);
}
}
int lca(int a, int b) {
if (lay[a] > lay[b]) swap(a, b);
int dif = lay[b] - lay[a];
for (int i = 17; i >= 0; i--) {
if (dif & (1 << i)) {
b = par[i][b];
}
}
if (a == b) return a;
for (int i = 17; i >= 0; i--) {
if (par[i][a] != par[i][b]) {
a = par[i][a];
b = par[i][b];
}
}
return par[0][a];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n,m; cin >> n >> m;
char ans[m];
fill(ans, ans + m, 'B');
d = DSU(n);
for (int i = 0; i < m; i++) {
int a,b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
graph.push_back({a,b});
ind[{a,b}] = i;
}
sort(graph.begin(), graph.end());
dfs1(1, 0);
sort(bridges.begin(), bridges.end());
for (auto [a,b] : bridges) {
int compa = d.find(a), compb = d.find(b);
comp[compa].push_back(compb);
comp[compb].push_back(compa);
compToOriginal[{min(compa, compb), max(compa, compb)}] = {a,b};
}
int root;
for (int v = 1; v <= n; v++) if (v == d.find(v)) {
root = v;
dfs2(root, root);
break;
}
int q; cin >> q;
while (q--) {
int a,b; cin >> a >> b;
a = d.find(a), b = d.find(b);
if (a == b) continue;
int L = lca(a,b);
while (a != L) {
int p = par[0][a];
auto [oldv, oldu] = compToOriginal[{min(a,p), max(a,p)}];
if (ind.find({oldv, oldu}) != ind.end()) {
int index = ind[{oldv, oldu}];
ans[index] = 'R';
} else {
int index = ind[{oldu, oldv}];
ans[index] = 'L';
}
a = p;
}
while (b != L) {
int p = par[0][b];
auto [oldu, oldv] = compToOriginal[{min(b,p), max(b,p)}];
if (ind.find({oldv, oldu}) != ind.end()) {
int index = ind[{oldv, oldu}];
ans[index] = 'R';
} else {
int index = ind[{oldu, oldv}];
ans[index] = 'L';
}
b = p;
}
}
for (char c : ans) cout << c;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3027 ms |
12632 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3027 ms |
12632 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3027 ms |
12632 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
