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 target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "boxes.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<61);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int n,m,i,fin[nmax],fup[nmax],br[nmax],x,y,l,tin,ex[nmax],ey[nmax],par[nmax][20],c[nmax],k,in[nmax],out[nmax],z,up[nmax],dw[nmax];
vector<int>a[nmax];
vector<pair<int,int> >g[nmax];
bitset<nmax>viz;
char rs[nmax];
void dfs(int x,int p=-1)
{
viz[x]=1;
fin[x]=fup[x]=++tin;
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==p)continue;
int y=x^ex[a[x][i]]^ey[a[x][i]];
if(viz[y])
{
fup[x]=min(fup[x],fin[y]);
}
else
{
dfs(y,a[x][i]);
fup[x]=min(fup[x],fup[y]);
if(fup[y]>fin[x])
{
br[a[x][i]]=1;
}
}
}
}
void col(int x)
{
viz[x]=1;
c[x]=k;
for(int i=0;i<a[x].size();i++)
{
int y=x^ex[a[x][i]]^ey[a[x][i]];
if(viz[y] || br[a[x][i]])continue;
col(y);
}
}
void con(int x)
{
viz[x]=1;
for(int i=0;i<a[x].size();i++)
{
int y=x^ex[a[x][i]]^ey[a[x][i]];
if(br[a[x][i]])
{
g[c[x]].pb(mkp(c[y],a[x][i]));
//g[c[y]].pb(c[x]);
continue;
}
if(viz[y])continue;
con(y);
}
}
void build(int x,int p)
{
viz[x]=1;
par[x][0]=p;
in[x]=++tin;
for(int i=1;i<18;i++)par[x][i]=par[par[x][i-1]][i-1];
for(int i=0;i<g[x].size();i++)
{
int y=g[x][i].fr;
if(y==p)continue;
build(y,x);
}
out[x]=++tin;
}
int anc(int x,int y)
{
return in[x]<=in[y] && out[y]<=out[x];
}
int lca(int x,int y)
{
if(anc(x,y))return x;
if(anc(y,x))return y;
for(int i=17;i>=0;i--)if(!anc(par[x][i],y))x=par[x][i];
return par[x][0];
}
void rec(int x,int p,int ed)
{
viz[x]=1;
for(int i=0;i<g[x].size();i++)
{
int y=g[x][i].fr;
if(y==p)continue;
rec(y,x,g[x][i].sc);
up[x]+=up[y];
dw[x]+=dw[y];
}
//cout<<x<<" "<<ed<<" "<<up[x]<<" "<<dw[x]<<endl;
if(up[x])
{
if(c[ex[ed]]==x)rs[ed]='R';
else rs[ed]='L';
}
if(dw[x])
{
if(c[ex[ed]]==x)rs[ed]='L';
else rs[ed]='R';
}
}
int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>n>>m;
for(i=1;i<=m;i++)
{
cin>>ex[i]>>ey[i];
a[ex[i]].pb(i);
a[ey[i]].pb(i);
}
for(i=1;i<=n;i++)
{
if(!viz[i])
{
dfs(i);
}
}
viz.reset();
for(i=1;i<=n;i++)
{
if(!viz[i])
{
k++;
col(i);
}
}
viz.reset();
for(i=1;i<=n;i++)
{
if(!viz[i])
{
con(i);
}
}
viz.reset();
for(i=1;i<=k;i++)
{
if(viz[i])continue;
build(i,i);
}
cin>>z;
while(z--)
{
cin>>x>>y;
x=c[x],y=c[y];
l=lca(x,y);
up[x]++;
up[l]--;
dw[y]++;
dw[l]--;
}
viz.reset();
for(i=1;i<=k;i++)
{
if(viz[i])continue;
rec(i,i,0);
}
for(i=1;i<=m;i++)
{
if(rs[i]=='L' || rs[i]=='R')cout<<rs[i];
else cout<<'B';
}
cout<<endl;
return 0;
}
Compilation message (stderr)
oneway.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization("O3")
oneway.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization("unroll-loops")
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a[x].size();i++)
~^~~~~~~~~~~~
oneway.cpp: In function 'void col(int)':
oneway.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a[x].size();i++)
~^~~~~~~~~~~~
oneway.cpp: In function 'void con(int)':
oneway.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a[x].size();i++)
~^~~~~~~~~~~~
oneway.cpp: In function 'void build(int, int)':
oneway.cpp:83:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[x].size();i++)
~^~~~~~~~~~~~
oneway.cpp: In function 'void rec(int, int, int)':
oneway.cpp:105:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[x].size();i++)
~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |