#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],ctr=1;
void dfs(int x,int pa){
low[x]=dep[x]=ctr++;
for(ii i:adj[x]){
if(dep[i.fi]==0){
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];
ii dir[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];
}
ii dfs4(int x){
ii cur=dir[x];
for(ii i:adj2[x]){
if(i.fi==par[0][x])continue;
ii s=dfs4(i.fi);
if(s.fi<=dep[x]){
int j=abs(idx[i.fi])-1;
if(s.se*idx[i.fi]>0)ans[j]='R';
else if(s.se*idx[i.fi]<0)ans[j]='L';
}
cur=min(cur,s);
}
return cur;
}
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]){
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]];
for(int i=1;i<c;i++)dir[i]=mp(INF,0);
scanf("%d",&p);
for(int i=0;i<p;i++){
scanf("%d%d",&a,&b);
a=comp[a];b=comp[b];
if(a==b)continue;
int l=lca(a,b);
dir[a]=min(dir[a],mp(dep[l],1));
dir[b]=min(dir[b],mp(dep[l],-1));
}
for(int i=1;i<c;i++){
if(!par[0][i]){
dfs4(i);
}
}
printf("%s",ans);
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
oneway.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
oneway.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | scanf("%d",&p);
| ~~~~~^~~~~~~~~
oneway.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5460 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
5460 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 |
2 ms |
5460 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 |
2 ms |
5460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
