#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
#define pii pair<int, int>
vector<pii> adj[maxn];
int n, m, p;
int ans[maxn];
stack<int> cs;
int dfs_num[maxn];
int dfs_low[maxn];
int dfs_counter;
bool vis[maxn];
int pa[maxn];
int par[18][maxn];
int n1[maxn], n2[maxn]; //give the sides for each edge
int mycomp[maxn]; //just store the maximum component
int dep[maxn];
vector<pii> adj2[maxn]; //modify the adj to be for bcc labels
int cp = 0;
pii edges[maxn];
void clearstack(int eid) {
vector<int> cur; //cur is a bcc of edges
while (!cs.empty() && cs.top() != eid) {
cur.push_back(cs.top()); cs.pop();
}
if (cs.size()) {
cur.push_back(cs.top()); cs.pop();
}
//now we do whatever cur processing we want
if (cur.size() == 1) {
//then it is a bridge
return;
}
//mark everything
// cout << cp + 1 << " component: " << endl;
++cp;
for (int val : cur) {
// cout << " " << val << " with " << n1[val] << " " << n2[val] << endl;
mycomp[n1[val]] = cp;
mycomp[n2[val]] = cp;
}
}
void dfs(int u, int p) {
dfs_num[u] = dfs_low[u] = dfs_counter++;
vis[u] = true;
int ch = 0;
for (auto vp : adj[u]) {
int v = vp.first;
int eid = vp.second;
if (eid == p) continue;
if (!vis[v]) {
cs.push(eid);
ch++;
pa[v] = u;
dfs(v, eid);
dfs_low[u] = min(dfs_low[u], dfs_low[v]);
if (pa[u] != -1 && dfs_low[v] >= dfs_num[u] ||
pa[u] == -1 && ch > 1) {
clearstack(eid);
}
}
else if (dfs_num[v] < dfs_num[u]) {
dfs_low[u] = min(dfs_low[u], dfs_num[v]);
cs.push(eid);
}
}
// cout << u << " goes to " << mycomp[u] << endl;
}
void dfsdown(int i, int p) {
vis[i] = true;
par[0][i] = p;
for (pii vp : adj2[i]) {
if (vp.first == p) continue;
dfsdown(vp.first, i);
}
}
int walk(int u, int k) {
for (int i = 17; i >= 0; i--) {
if (k & (1 << i)) {
u = par[i][u];
}
}
return u;
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
u = walk(u, dep[u] - dep[v]);
if (u == v) return 0;
for (int i = 17; i >= 0; i--) {
if (par[i][u] != par[i][v]) {
u = par[i][u];
v = par[i][v];
}
}
return par[0][u];
}
int mydelt[maxn];
void dfsans(int u, int eid) {
if (vis[u]) return;
vis[u] = true;
for (pii vp : adj2[u]) {
if (vp.second == eid) continue;
dfsans(vp.first, vp.second);
mydelt[u] += mydelt[vp.first];
}
if (mydelt[u] > 0) {
//it points upwards
if (mycomp[n1[eid]] == u) {
ans[eid] = 2;
}
else ans[eid] = 1;
}
else if (mydelt[u] < 0) {
//edge points downwards
if (mycomp[n1[eid]] == u) {
ans[eid] = 1;
}
else ans[eid] = 2;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;;
//m pairs follow with road from a to b
// can be multiple edges or self-loops (throw out the latter)
int a, b;
int cid = 0;
for (int i = 1; i <= m; i++) {
cin >> a >> b;
edges[i] = pii(a, b);
++cid;
if (a == b) continue; //we don't need this
adj[a].push_back(pii(b, cid));
adj[b].push_back(pii(a, cid));
n1[cid] = a;
n2[cid] = b;
}
cin >> p;
//p pairs follow giving constraints that we must be able to go x to y
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
pa[i] = -1;
dfs(i, -1);
clearstack(-1);
}
}
for (int i = 1; i <= n; i++) {
if (mycomp[i] == 0) mycomp[i] = ++cp;
}
//something like do the actual answer loop
//first construct adj2
for (int i = 1; i <= m; i++) {
a = edges[i].first;
b = edges[i].second;
if (mycomp[a] != mycomp[b]) {
adj2[mycomp[a]].push_back(pii(mycomp[b], i));
adj2[mycomp[b]].push_back(pii(mycomp[a], i));
}
}
fill(vis, vis+maxn, false);
// for (int i = 1; i <= n; i++) {
// cout << i << " is in " << mycomp[i] << endl;
// }
for (int i = 1; i <= cp; i++) {
if (!vis[i]) dfsdown(i, -1);
}
for (int i = 1; i < 18; i++) {
for (int u = 1; u <= cp; u++) {
if (par[i-1][u] != -1) {
par[i][u] = par[i-1][par[i-1][u]];
}
else par[i][u] = -1;
}
}
int x, y;
for (int i = 0; i < p; i++) {
cin >> x >> y;
x = mycomp[x];
y = mycomp[y];
int lc = lca(x, y);
mydelt[x]++;
mydelt[lc]--;
mydelt[y]--;
mydelt[lc]++;
}
fill(vis, vis+maxn, false);
for (int i = 1; i <= cp; i++) {
if (!vis[i]) dfsans(i, -1);
}
for (int i = 1; i <= m; i++) {
if (ans[i] == 0) cout << "B";
if (ans[i] == 1) cout << "L";
if (ans[i] == 2) cout << "R";
}
cout << endl;
}
Compilation message
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:64:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (pa[u] != -1 && dfs_low[v] >= dfs_num[u] ||
~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5240 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5240 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5240 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
