#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
typedef vector<int> vi;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;
int n,m,p;
ii edge[100005];
vector<ii> adj[100005],adj2[100005];
bool bridge[100005];
char ans[100005];
int dep[100005],low[100005];
void dfs(int x,int pa){
low[x]=dep[x];
for(ii i:adj[x]){
if(dep[i.fi]==0){
dep[i.fi]=dep[x]+1;
dfs(i.fi,x);
if(low[i.fi]>dep[x])bridge[abs(i.se)]=1;
else low[x]=min(low[i.fi],low[x]);
}else if(i.fi!=pa)low[x]=min(dep[i.fi],low[x]);
}
}
int comp[100005],c=1;
void dfs2(int x){
comp[x]=c;
for(ii i:adj[x]){
if(bridge[abs(i.se)])continue;
if(comp[i.fi])continue;
dfs2(i.fi);
}
}
int par[20][100005];
int dir[20][100005];
int idx[100005];
void dfs3(int x){
for(ii i:adj2[x]){
if(i.fi==par[0][x])continue;
dep[i.fi]=dep[x]+1;
par[0][i.fi]=x;
idx[i.fi]=-i.se;
dfs3(i.fi);
}
}
int lca(int x,int y){
if(dep[x]>dep[y])swap(x,y);
for(int i=19;i>=0;i--)if(dep[par[i][y]]>=dep[x])y=par[i][y];
if(x==y)return x;
for(int i=19;i>=0;i--)if(par[i][x]!=par[i][y])x=par[i][x],y=par[i][y];
return par[0][x];
}
void direct(int x,int y,int d){
for(int i=19;i>=0;i--){
if(dep[par[i][x]]>=dep[y]){
dir[i][x]=d;
x=par[i][x];
}
}
}
int main(){
scanf("%d%d",&n,&m);
int a,b;
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
edge[i]=mp(a,b);
adj[a].pb(b,i);
adj[b].pb(a,-i);
}
for(int i=1;i<=n;i++){
if(!dep[i]){
dep[i]=1;
dfs(i,0);
}
}
for(int i=1;i<=n;i++){
if(!comp[i]){
dfs2(i);
c++;
}
}
for(int i=1;i<=m;i++){
ans[i-1]='B';
if(bridge[i]){
a=comp[edge[i].fi],b=comp[edge[i].se];
adj2[a].pb(b,i);
adj2[b].pb(a,-i);
}
}
memset(dep,0,sizeof(dep));
for(int i=1;i<c;i++){
if(!par[0][i]){
dep[i]=1;
dfs3(i);
}
}
for(int i=1;i<20;i++)for(int j=1;j<c;j++)par[i][j]=par[i-1][par[i-1][j]];
scanf("%d",&p);
for(int i=0;i<p;i++){
scanf("%d%d",&a,&b);
if(comp[a]==comp[b])continue;
int l=lca(comp[a],comp[b]);
direct(comp[a],l,1);
direct(comp[b],l,-1);
}
for(int i=19;i>0;i--){
for(int j=1;j<c;j++){
if(dir[i][j]!=0){
dir[i-1][j]=dir[i][j];
dir[i-1][par[i-1][j]]=dir[i][j];
}
}
}
for(int i=1;i<c;i++){
if(idx[i]==0)continue;
if(dir[0][i]*idx[i]>0)ans[abs(idx[i])-1]='R';
else if(dir[0][i]*idx[i]<0)ans[abs(idx[i])-1]='L';
}
printf("%s",ans);
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
oneway.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
oneway.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%d",&p);
| ~~~~~^~~~~~~~~
oneway.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5460 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5460 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5460 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
