#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ll long long
using namespace std;
const int N = 1e5 + 5;
int n,m,p;
int x,y;
int P[N][21];
vector<pair<int,int>>gr[N];
pair<int,int> edge[N];
char answer[N];
int in[N], out[N];
int timer, root;
vector<int> roots;
int A[N], B[N], fix[N], fixA[N], fixB[N], lvl[N], dp[N];
void dfs(int x,int par){
timer++;
in[x] = timer;
P[x][0] = par;
for(int i = 1; i <= 20; i++){
P[x][i] = P[P[x][i-1]][i-1];
}
fix[x] = 1;
for(auto p : gr[x]){
int to = p.ff;
int ind = p.ss;
if(!fix[to]){
lvl[to] = lvl[x] + 1;
dfs(to,x);
dp[x] += dp[to];
continue;
}
if(to == par) continue;
if(lvl[to] < lvl[x]){
dp[x]++;
} else {
dp[x]--;
}
}
//cout << dp[x] << " " << x << endl;
//if(dp[x] == 0 && x != root){
//cout << x << endl;
//}
out[x] = timer;
}
inline bool check(int x,int y){
return in[x] <= in[y] && out[x] >= out[y];
}
inline int lca(int x,int y){
if(check(x,y)) return x;
if(check(y,x)) return y;
for(int i = 20; i >= 0; i--){
if(P[x][i] && !check(P[x][i],y)){
x = P[x][i];
}
}
return P[x][0];
}
void dfsA(int x,int ind){
fixA[x] = 1;
for(auto p : gr[x]){
int to = p.ff;
int ind = p.ss;
if(fixA[to]) continue;
dfsA(to,ind);
A[x] += A[to];
}
if(A[x] && dp[x] == 0){
//cout << x << endl;
if(edge[ind].ff == x) answer[ind] = 'R'; else answer[ind] = 'L';
}
}
void dfsB(int x,int ind){
fixB[x] = 1;
for(auto p : gr[x]){
int to = p.ff;
int ind = p.ss;
if(fixB[to]) continue;
dfsB(to,ind);
B[x] += B[to];
}
if(B[x] && dp[x] == 0){
if(edge[ind].ff == x) answer[ind] = 'L'; else answer[ind] = 'R';
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x,y;
cin >> x >> y;
edge[i] = {x,y};
gr[x].pb({y,i});
gr[y].pb({x,i});
}
for(int i = 1; i <= n; i++){
if(fix[i]) continue;
root = i;
roots.pb(root);
dfs(i,0);
}
//cout << "done dfs" << endl;
cin >> p;
while(p--){
int x,y;
cin >> x >> y;
int z = lca(x,y); cout << z << endl;
A[x] ++; A[z] --;
B[y] ++; B[z] --;
}
//cout << "done p" << endl;
for(int i = 1; i <= m; i++) answer[i] = 'B';
for(auto root : roots){
dfsA(root, 0);
}
//cout << "done dfsA" << endl;
for(auto root : roots){
dfsB(root, 0);
}
for(int i = 1; i <= m; i++){
cout << answer[i] ;
}
cout << endl;
}
Compilation message
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:33:21: warning: unused variable 'ind' [-Wunused-variable]
int ind = p.ss;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
