#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=100010;
const ll mod=1000000007;
const ll inf=1e15;
int a[N],b[N];
int x[N],y[N];
vector<pair<int,int> >g[N];
int timer=0;
int tin[N],tout[N],fup[N];
bool used[N];
bool imp[N];
void dfs(int v,int pr){
used[v]=true;
tin[v]=fup[v]=++timer;
for (auto cur:g[v]){
int to=cur.first;
int ind=cur.second;
if (ind==pr) continue;
if (!used[to]){
dfs(to,ind);
if (fup[to]>tin[v]) imp[ind]=true;
fup[v]=min(fup[v],fup[to]);
} else {
fup[v]=min(fup[v],tin[to]);
}
}
}
int comp[N];
int num=0;
void dfs1(int v){
comp[v]=num;
for (auto cur:g[v]){
int to=cur.first;
int ind=cur.second;
if (!imp[ind] && !comp[to]){
dfs1(to);
}
}
}
vector<pair<int,int> >t[N];
const int L=20;
int up[N][L];
void dfs2(int v,int pr){
up[v][0]=pr;
// cout<<"0 "<<v<<" "<<pr<<endl;
for (int i=1;i<L;i++){
up[v][i]=up[up[v][i-1]][i-1];
}
used[v]=true;
tin[v]=++timer;
for (auto cur:t[v]){
int to=cur.first;
int ind=cur.second;
if (to==pr) continue;
dfs2(to,v);
}
tout[v]=timer;
}
bool upper(int a,int b){
return (tin[a]<=tin[b] && tout[b]<=tout[a]);
}
int lca(int a,int b){
if (upper(a,b)) return a;
if (upper(b,a)) return b;
for (int i=L-1;i>=0;i--){
if (!upper(up[a][i],b)) a=up[a][i];
}
return up[a][0];
}
int add[N][2];
char ans[N];
void dfs3(int v,int pr,int ind){
used[v]=true;
for (auto cur:t[v]){
int to=cur.first;
int ind=cur.second;
if (to==pr) continue;
dfs3(to,v,ind);
add[v][0]+=add[to][0];
add[v][1]+=add[v][1];
}
// if (add[v][0] && add[v][1]) exit(1);
if (add[v][0]){
if (comp[a[ind]]==v) ans[ind]='R';
else ans[ind]='L';
} else if (add[v][1]){
if (comp[a[ind]]==v) ans[ind]='L';
else ans[ind]='R';
} else {
}
}
pair<int,int> p[N];
void dfs4(int v){
used[v]=true;
for (auto cur:t[v]){
int to=cur.first;
int ind=cur.second;
if (used[to]) continue;
p[to]={v,ind};
dfs4(to);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,m;cin>>n>>m;
for (int i=1;i<=m;i++){
cin>>a[i]>>b[i];
g[a[i]].push_back({b[i],i});
g[b[i]].push_back({a[i],i});
ans[i]='B';
}
int k;cin>>k;
for (int i=1;i<=k;i++){
cin>>x[i]>>y[i];
}
for (int i=1;i<=n;i++){
if (!used[i]){
dfs(i,0);
}
}
for (int i=1;i<=n;i++){
if (!comp[i]){
num++;
dfs1(i);
}
}
for (int v=1;v<=n;v++){
for (auto cur:g[v]){
int to=cur.first;
int ind=cur.second;
if (imp[ind]){
t[comp[v]].push_back({comp[to],ind});
}
}
}
for (int i=1;i<=k;i++){
x[i]=comp[x[i]];
y[i]=comp[y[i]];
}
for (int i=1;i<=k;i++){
for (int j=1;j<=n;j++) used[j]=false;
dfs4(x[i]);
int cur=y[i];
while (cur!=x[i]){
int to=p[cur].first;
int ind=p[cur].second;
if (comp[a[ind]]==to) ans[ind]='R';
else ans[ind]='L';
cur=to;
}
}
for (int i=1;i<=n;i++) used[i]=false,tin[i]=0;
tin[0]=0;
timer=0;
for (int i=1;i<=num;i++){
if (!used[i]) dfs2(i,0);
}
tout[0]=timer;
for (int i=1;i<=k;i++){
int lc=lca(x[i],y[i]);
add[x[i]][0]++;
add[y[i]][1]++;
add[lc][0]--;
add[lc][1]--;
}
for (int i=1;i<=num;i++) used[i]=false;
for (int i=1;i<=num;i++) {
if (!used[i]){
dfs3(i,0,0);
}
}
for (int i=1;i<=m;i++) cout<<ans[i];
cout<<endl;
return 0;
}
Compilation message
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:57:13: warning: unused variable 'ind' [-Wunused-variable]
57 | int ind=cur.second;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
5188 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
5188 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
5188 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
