This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<pii> vii;
#define cont(x) for(auto el:x) {cout<<el<<' ';} cout<<endl;
#define endl '\n'
#define contp(x) for(auto el:x) {cout<<el.fi<<'-'<<el.se<<' ';} cout<<endl;
#define pb push_back
#define sp <<' '<<
#define DEBUG(x) {cout<<(#x) sp x<<endl;}
#define carp(x,y) ((x%MOD)*(y%MOD))%MOD
#define topla(x,y) ((x%MOD)+(y%MOD))%MOD
const int MAXN=1e5+5;
int n,m;
vi adj[MAXN];
int tane[MAXN], dep[MAXN], low[MAXN], p[MAXN], comp[MAXN];
bool vis[MAXN], isbridge[MAXN];
map<pii,int> ind;
vii edge;
int say;
vii g[MAXN];
vector<char> ans;
set<pii> tut;
void dfs(int nd,int ata,int h){
dep[nd]=h;
low[nd]=h;
p[nd]=ata;
for(auto kom:adj[nd]){
if(kom==ata) continue;
if(vis[kom]){
if(dep[kom]<dep[nd]){ //back edge
low[nd]=min(low[nd],dep[kom]);
}
continue;
}
vis[kom]=true;
dfs(kom,nd,h+1);
low[nd]=min(low[nd],low[kom]);
}
if(ata!=0 and low[nd]>=dep[nd] and tane[ind[{ata,nd}]]<=1){
isbridge[ind[{ata,nd}]]=true;
edge.pb({ata,nd});
}
}
void dfs2(int nd){ //componentlere ayir
comp[nd]=say;
for(auto kom:adj[nd]){
if(kom==p[nd]) continue;
if(vis[kom]) continue;
if(isbridge[ind[{nd,kom}]]) continue;
vis[kom]=true;
dfs2(kom);
}
}
int top[MAXN];
void dfs3(int nd,int ata,int ind){
for(auto el:g[nd]){
int kom=el.fi;
int yer=el.se;
if(kom==ata) continue;
dfs3(kom,nd,yer);
top[nd]+=top[kom];
}
//cout<<"here" sp nd sp ata sp ind sp top[nd]<<endl;
if(top[nd]<0){ //bana edge çek
if(tut.count({ata,nd})) ans[ind]='R';
else ans[ind]='L';
}
else if(top[nd]>0){ //benden edge çek
if(tut.count({ata,nd})) ans[ind]='L';
else ans[ind]='R';
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
set<pii> temp;
FOR(i,m){
int a,b;
cin>>a>>b;
adj[a].pb(b);
adj[b].pb(a);
//yeni bir edgese
if(ind[{a,b}]==0) ind[{a,b}]=ind[{b,a}]=i+1;
tane[ind[{a,b}]]++;
temp.insert({a,b});
}
FORE(i,1,n+1){
if(!vis[i]){
vis[i]=true;
dfs(i,0,0);
}
}
FORE(i,1,n+1) vis[i]=false;
//contp(edge);
say=1;
FORE(i,1,n+1){
if(!vis[i]){
vis[i]=true;
dfs2(i);
say++;
}
}
for(auto el:temp) tut.insert({comp[el.fi],comp[el.se]});
//FORE(i,1,n+1) cout<<comp[i]<<' ';
//cout<<endl;
//create the condensation graph
for(auto el:edge){
g[comp[el.fi]].pb({comp[el.se],ind[el]});
g[comp[el.se]].pb({comp[el.fi],ind[el]});
}
int p;
cin>>p;
while(p--){
int a,b;
cin>>a>>b;
top[comp[a]]++;
top[comp[b]]--;
}
ans.resize(m+1,'B');
FORE(i,1,n+1) vis[i]=false;
dfs3(1,0,0);
FORE(i,1,m+1) cout<<ans[i];
cout<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |