#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN=1e5;
int n, m, k, eu[mxN], ev[mxN], t, ecc, tin[mxN], low[mxN], who[mxN], d[mxN], anc[mxN][17], dp[mxN][2];
vector<int> adj[mxN];
stack<int> st;
vector<ar<int, 2>> br, adj2[mxN];
char ans[mxN];
void make(int u) {
who[u]=ecc;
while(st.top()^u)
who[st.top()]=ecc, st.pop();
st.pop(), ++ecc;
}
void dfs(int u, int p=-1) {
tin[u]=low[u]=++t;
st.push(u);
for (int i : adj[u]) {
if (i==p)
continue;
int v=u^eu[i]^ev[i];
if (!tin[v]) {
dfs(v, i);
low[u]=min(low[u], low[v]);
if (low[v]>tin[u]) { // bridge
//cout << "bridge: " << u << " " << v << endl;
br.push_back({i, u==eu[i]});
make(v);
}
} else
low[u]=min(low[u], tin[v]);
}
}
void dfs2(int u, int p=-1) {
//cout << u << endl;
anc[u][0]=p;
for (int i=1; i<17; ++i)
anc[u][i]=anc[anc[u][i-1]][i-1];
for (ar<int, 2> x : adj2[u]) {
int v=u^who[eu[x[0]]]^who[ev[x[0]]];
d[v]=d[u]+1;
dfs2(v, u);
}
}
int lca(int u, int v) {
if (d[u]>d[v])
swap(u, v);
for (int i=16; ~i; --i)
if (d[u]<=d[v]-(1<<i))
v=anc[v][i];
if (u==v)
return u;
for (int i=16; ~i; --i)
if (anc[u][i]^anc[v][i])
u=anc[u][i], v=anc[v][i];
return anc[u][0];
}
void dfs3(int u) {
for (ar<int, 2> x : adj2[u]) {
int v=u^who[eu[x[0]]]^who[ev[x[0]]];
dfs3(v);
dp[u][0]+=dp[v][0];
dp[u][1]+=dp[v][1];
assert(!(dp[v][0]&&dp[v][1]));
if (dp[v][0]||dp[v][1])
ans[x[0]]=x[1]^dp[v][0]>0?'R':'L';
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i=0; i<m; ++i) {
cin >> eu[i] >> ev[i], --eu[i], --ev[i];
adj[eu[i]].push_back(i);
adj[ev[i]].push_back(i);
}
for (int i=0; i<n; ++i) {
if (tin[i])
continue;
dfs(i);
make(i);
for (ar<int, 2> b : br) {
int u=b[1]?eu[b[0]]:ev[b[0]];
adj2[who[u]].push_back(b);
}
dfs2(who[i]);
}
cin >> k;
for (int i=0; i<k; ++i) {
int u, v;
cin >> u >> v, --u, --v;
u=who[u], v=who[v];
int uv=lca(u, v);
++dp[u][0], --dp[uv][0];
++dp[v][1], --dp[uv][1];
}
memset(ans, 'B', m);
for (int i=0; i<ecc; ++i)
if (anc[i][0]==-1)
dfs3(i);
for (int i=0; i<m; ++i)
cout << ans[i];
return 0;
}
Compilation message
oneway.cpp: In function 'void dfs3(int)':
oneway.cpp:75:27: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
75 | ans[x[0]]=x[1]^dp[v][0]>0?'R':'L';
| ~~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
10080 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
10080 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
10080 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
