#include <bits/stdc++.h>
using namespace std;
#define Go ios_base::sync_with_stdio(false);cin.tie(NULL)
#define endl "\n"
#define ll long long
// =========================================================================================
////////////////////////////////////////////////////////////////////////////////////////////
// Bridges Decomposition
// comid : number of cur components and it's the index in bcc
// bcc : will contain each component separately
// in[i] : entry time for node i
// up[i] : min (in[w]) such that there is an edge u - w and u in the subtree of i
// cur : stack to keep the curren nodes which are not in a bcc yet
// edg : same as cur but for edges
// com[i] : the id of the bcc of the node i
// badj : adj for the bridges-tree
// vadj : adj for the A-tree
// bcc : 2-edge connected components
// bcc[i] : will contain the nodes of componenet i
// and connected components are seperated using bridges
// acc : 2-vertex connected components
// acc[i] : will contain the edges of component i
// and connected components are seperated using A points
struct BCC {
int n, m, tick, comid, edgeid, accid;
vector<vector<pair<int, int>>> adj, badj; // to, edge number
vector<pair<int, int>> bridges;
vector<vector<int>> bcc, vadj, acc;
vector<int> up, in, cur, com, edg, acom;
vector<bool> visedge, isbridge, Ap;
BCC() { }
BCC(int n, int m) { init(n, m); }
void init(int n, int m) {
this->n = n; this->m = m;
tick = comid = edgeid = accid = 0;
bridges.clear();
adj.assign(n + 1, { });
bcc.assign(1, { });
acc.assign(1, { });
up.assign(n + 1, 0);
Ap.assign(n + 1, 0);
in.assign(n + 1, 0);
acom.assign(m + 1, 0);
com.assign(n + 1, 0);
isbridge.assign(m + 1, 0);
visedge.assign(m + 1, 0);
}
void addedge(int x, int y) {
edgeid++;
adj[x].push_back({ y, edgeid });
adj[y].push_back({ x, edgeid });
}
void build() {
for (int i = 1; i <= n; i++) {
if (!in[i]) dfs(i, 0, -1);
}
}
void dfs(int node, int p, int comming) {
up[node] = in[node] = ++tick;
cur.push_back(node);
int childes = 0;
for (auto& c : adj[node]) {
int u = c.first, id = c.second;
if (visedge[id]) continue;
edg.push_back(id);
visedge[id] = 1;
if (in[u]) {
up[node] = min(up[node], in[u]);
continue;
}
childes++;
dfs(u, node, id);
up[node] = min(up[node], up[u]);
if (up[u] >= in[node] || Ap[node]) {
Ap[node] = 1;
acc.emplace_back();
accid++;
while (true) {
int x = edg.back(); edg.pop_back();
acc.back().push_back(x);
acom[x] = accid;
if (x == id) break;
}
}
}
if (up[node] > in[p]) {
if (p) {
bridges.push_back({ node, p });
isbridge[comming] = 1;
}
comid++;
bcc.emplace_back();
for (; !cur.empty() && in[cur.back()] >= in[node]; cur.pop_back()) {
bcc[comid].push_back(cur.back());
com[cur.back()] = comid;
}
}
if (!p) Ap[node] = childes > 1;
}
void BuildBridgesTree() {
badj.assign(n + 1, { });
for (int i = 1; i <= n; i++) {
for (auto& j : adj[i]) {
if (com[i] != com[j.first]) {
badj[com[i]].push_back({ com[j.first], j.second });
badj[com[j.first]].push_back({ com[i], j.second });
}
}
}
for (int i = 1; i <= n; i++) {
sort(badj[i].begin(), badj[i].end());
badj[i].erase(unique(badj[i].begin(), badj[i].end()), badj[i].end());
}
}
void BuildArtiTree() {
vadj.assign(m + n + 2, { });
int c = m;
for (int i = 1; i <= n; i++) {
if (!Ap[i]) continue;
c++;
for (auto& j : adj[i]) {
vadj[c].push_back(acom[j.second]);
vadj[acom[j.second]].push_back(c);
}
}
for (int i = 1; i <= c; i++) {
sort(vadj[i].begin(), vadj[i].end());
vadj[i].erase(unique(vadj[i].begin(), vadj[i].end()), vadj[i].end());
}
}
};
void Burn_The_Problem_Alive() {
int n; cin >> n;
int m; cin >> m;
BCC b(n, m);
vector<vector<int>> edges(1);
for (int x, y, i = 1; i <= m; i++) {
cin >> x >> y;
b.addedge(x, y);
edges.push_back({ x, y });
}
b.build();
b.BuildBridgesTree();
string ans(n + 1, 'B');
vector<int> val(m + 1);
int q; cin >> q;
vector<int> in(n + 1), out(n + 1), vis(n + 1);
int tick = 0;
function<void(int, int)> fun = [&](int node, int p) {
in[node] = ++tick;
for (auto& u : b.badj[node]) {
if (u.first != p) fun(u.first, node);
}
out[node] = ++tick;
};
for (int i = 1; i <= n; i++) {
if (!in[i])
fun(i, 0);
}
while (q--) {
int x, y; cin >> x >> y;
val[b.com[x]]++;
val[b.com[y]]--;
}
function < void(int, int, int) > dfs = [&](int node, int p, int comming) {
vis[node] = 1;
for (auto& u : b.badj[node]) {
if (u.first == p) continue;
dfs(u.first, node, u.second);
val[node] += val[u.first];
}
if (val[node] > 0) {
if (b.com[edges[comming][0]] == p) {
ans[comming] = 'L';
}
else ans[comming] = 'R';
}
else if (val[node] < 0) {
if (b.com[edges[comming][0]] == p) {
ans[comming] = 'R';
}
else ans[comming] = 'L';
}
};
for (int i = 1; i <= n; i++) {
if (!vis[i])
dfs(i , 0, 0);
}
for (int i = 1; i <= m; i++)cout << ans[i];
}
// =========================================================================================
int32_t main() {
Go;
int TES = 1; // cin >> TES;
while (TES--)Burn_The_Problem_Alive();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
