#include<bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
const int MAXN = 100009;
const int LOG = 17;
int n, m;
int jump[MAXN];
bool bridge[MAXN];
int dep[MAXN];
vector<pii> G[MAXN];
vector<pii> G2[MAXN];
int S[MAXN];
int E[MAXN];
pii edge[MAXN];
int ans[MAXN];
bool vis[MAXN];
int tab[MAXN];
int cnt;
int T, tin[MAXN], tout[MAXN], jp2[MAXN][LOG];
void dfs1(int x, int d, int pre) {
vis[x] = true;
dep[x] = d;
jump[x] = d;
for(auto [z, id]:G[x]) {
if(id==pre) continue;
if(!vis[z]) {
dfs1(z, d+1, id);
jump[x] = min(jump[x], jump[z]);
} else {
jump[x] = min(jump[x], dep[z]);
}
}
if(pre==-1) return;
if(jump[x] == d) bridge[pre] = true;
//cout << "teraz: " << x << " skok: " << jump[x] << "\n";
//cout << pre << " " << bridge[pre] << "\n";
}
void dfs2(int x, int col) {
vis[x] = true;
tab[x] = col;
for(auto [z, id]:G[x]) {
if(!bridge[id]) {
if(!vis[z]) dfs2(z, col);
} else {
if(vis[z]) {
G2[col].pb({tab[z], id});
} else {
dfs2(z, ++cnt);
G2[col].pb({tab[z], id});
}
}
}
}
void dfs3(int x, int y) {
//cout << "licze: " << x << " " << y << "\n";
vis[x] = true;
tin[x] = ++T;
jp2[x][0] = y;
for(int i=1;i<LOG;i++) {
jp2[x][i] = jp2[jp2[x][i-1]][i-1];
}
for(auto [z, id]:G2[x]) {
if(z!=y) dfs3(z, x);
}
tout[x] = ++T;
}
bool is_ancestor(int x, int y) {
return tin[x]<=tin[y]&&tout[x]>=tout[y];
}
int lca(int x, int y) {
if(is_ancestor(x, y)) return x;
if(is_ancestor(y, x)) return y;
for(int i=LOG-1;i>=0;i--) {
if(!is_ancestor(jp2[x][i], y)) {
x = jp2[x][i];
}
}
return jp2[x][0];
}
pii dfs4(int x, int pre) {
vis[x] = true;
pii val = {0, 0};
for(auto [z, id]:G2[x]) {
if(id==pre) continue;
pii nval = dfs4(z, id);
val.st += nval.st;
val.nd += nval.nd;
}
val.st += S[x];
val.nd += E[x];
//cout << "v: " << x << " " << val.st << " " << val.nd << "\n";
assert(!val.st||!val.nd);
if(pre==-1) return val;
if(S[x]) {
if(x == edge[pre].st) {
ans[pre] = 1;
} else {
ans[pre] = -1;
}
} else {
if(x == edge[pre].st) {
ans[pre] = -1;
} else {
ans[pre] = 1; }
}
return val;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i=0;i<m;i++) {
int a, b;
cin >> a >> b;
G[a].pb({b, i});
G[b].pb({a, i});
edge[i] = {a, b};
}
for(int i=1;i<=n;i++) {
if(!vis[i]) {
dfs1(i, 0, -1);
}
}
memset(vis, 0, sizeof(vis));
for(int i=1;i<=n;i++) {
if(!vis[i]) {
dfs2(i, ++cnt);
}
}
for(int i=1;i<=n;i++) {
//cout << i << ": " << tab[i] << "\n";
}
//cout << "graf\n";
for(int i=1;i<=cnt;i++) {
//cout << i << ":\n";
for(pii x:G2[i]) {
//cout << x.st << " " << x.nd << "\n";
}
}
//cout << "koniec\n";
memset(vis, 0, sizeof(vis));
for(int i=1;i<=cnt;i++) {
if(!vis[i]) {
dfs3(i, 0);
}
}
tin[0] = 0;
tout[0] = ++T;
int q;
cin >> q;
while(q--) {
int a, b;
cin >> a >> b;
S[tab[a]]++;
E[tab[b]]++;
int Lca = lca(tab[a], tab[b]);
//cout << tab[a] << " " << tab[b] << " " << Lca << " lca\n";
S[Lca]--;
E[Lca]--;
}
for(int i=1;i<=cnt;i++) {
//cout << i << ": "<< S[i] << " " << E[i] << "\n";
}
memset(vis, 0, sizeof(vis));
for(int i=1;i<=cnt;i++) {
if(!vis[i]) {
dfs4(i, -1);
}
}
for(int i=0;i<m;i++) {
if(ans[i]==0) {
cout << "B";
} else if(ans[i]==1) {
cout << "L";
} else {
cout << "R";
}
}
cout << "\n";
}
Compilation message
oneway.cpp: In function 'int32_t main()':
oneway.cpp:153:11: warning: variable 'x' set but not used [-Wunused-but-set-variable]
153 | for(pii x:G2[i]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
