//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "rail.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<<62);
const int inf=(1<<30);
const ll nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int i,n,m,x,y,fin[nmax],fup[nmax],tim,viz[nmax],vl[nmax],val[nmax],k,nr,vb[nmax],up[nmax][20],tin[nmax],tout[nmax],t,l,r,j,var[nmax],pr[nmax],e[nmax];
char rs[nmax];
pair<int,int>edg[nmax];
vector<pair<int,int> >a[nmax],gr[nmax];
vector<int>brg,vc,q[nmax];
void dfs(int x,int p)
{
viz[x]=1;
fin[x]=fup[x]=tim++;
for(int i=0;i<a[x].size();i++)
{
if(a[x][i].fr==p)continue;
if(viz[a[x][i].fr])fup[x]=min(fup[x],fin[a[x][i].fr]);
else
{
dfs(a[x][i].fr,x);
fup[x]=min(fup[x],fup[a[x][i].fr]);
if(fup[a[x][i].fr]>fin[x])brg.pb(a[x][i].sc);
}
}
}
void dfs2(int x)
{
viz[x]=1;
vl[x]=k;
for(int i=0;i<a[x].size();i++)
{
if(viz[a[x][i].fr] || vb[a[x][i].sc])continue;
dfs2(a[x][i].fr);
}
}
void dfs3(int x,int p,int ed)
{
for(int i=0;i<gr[x].size();i++)
{
if(gr[x][i].fr==p)continue;
dfs3(gr[x][i].fr,x,gr[x][i].sc);
val[x]+=val[gr[x][i].fr];
var[x]+=var[gr[x][i].fr];
}
if(val[x]>0 && ed)
{
if(vl[edg[ed].fr]==x)rs[ed]='R';
else rs[ed]='L';
}
if(var[x]>0 && ed)
{
if(vl[edg[ed].fr]==x)rs[ed]='L';
else rs[ed]='R';
}
}
void bld(int x,int p,int ed)
{
viz[x]=1;
vc.pb(x);
tin[x]=++t;
up[x][0]=p,pr[x]=p;
e[x]=ed;
for(int i=1;i<18;i++)up[x][i]=up[up[x][i-1]][i-1];
for(int i=0;i<gr[x].size();i++)if(gr[x][i].fr!=p)bld(gr[x][i].fr,x,gr[x][i].sc);
tout[x]=++t;
}
int anc(int x,int y)
{
return tin[x]<=tin[y] && tout[x]>=tout[y];
}
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(up[x][i],y))x=up[x][i];
return up[x][0];
}
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>>x>>y;
a[x].pb(mkp(y,i));
a[y].pb(mkp(x,i));
edg[i]=mkp(x,y);
}
//memset(fin,-1,sizeof(fin));
//memset(fup,-1,sizeof(fup));
for(i=1;i<=n;i++)
{
if(viz[i])continue;
dfs(i,i);
}
for(i=0;i<brg.size();i++)vb[brg[i]]=1;
for(i=1;i<=m;i++)rs[i]='B';
memset(viz,0,sizeof(viz));
for(i=1;i<=n;i++)
{
if(viz[i])continue;
k++;
dfs2(i);
//cout<<k<<" "<<i<<endl;
}
for(i=1;i<=n;i++)
{
for(j=0;j<a[i].size();j++)
{
if(vb[a[i][j].sc])
{
gr[vl[i]].pb(mkp(vl[a[i][j].fr],a[i][j].sc));
//cout<<vl[i]<<" "<<vl[a[i][j].fr]<<endl;
}
}
}
cin>>nr;
for(i=1;i<=nr;i++)
{
cin>>x>>y;
if(vl[x]!=vl[y])q[vl[x]].pb(vl[y]);
}
memset(viz,0,sizeof(viz));
for(i=1;i<=k;i++)
{
if(viz[i])continue;
vc.clear();
bld(i,i,0);
for(j=0;j<vc.size();j++)
{
x=vc[j];
for(r=0;r<q[x].size();r++)
{
l=lca(q[x][r],x);
/*val[x]++;
val[l]--;
var[q[x][r]]++;
var[l]--;*/
y=x;
while(y!=l)
{
if(vl[edg[e[y]].fr]==y)rs[e[y]]='R';
else rs[e[y]]='L';
y=pr[y];
if(!y || y==i)break;
}
y=q[x][r];
while(y!=l)
{
if(vl[edg[e[y]].fr]==y)rs[e[y]]='L';
else rs[e[y]]='R';
y=pr[y];
if(!y || y==i)break;
}
}
}
//dfs3(i,0,0);
}
for(i=1;i<=m;i++)cout<<rs[i];
cout<<endl;
return 0;
}
Compilation message
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a[x].size();i++)
~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int)':
oneway.cpp:47: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 dfs3(int, int, int)':
oneway.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<gr[x].size();i++)
~^~~~~~~~~~~~~
oneway.cpp: In function 'void bld(int, int, int)':
oneway.cpp:81:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<gr[x].size();i++)if(gr[x][i].fr!=p)bld(gr[x][i].fr,x,gr[x][i].sc);
~^~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:116:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<brg.size();i++)vb[brg[i]]=1;
~^~~~~~~~~~~
oneway.cpp:128:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<a[i].size();j++)
~^~~~~~~~~~~~
oneway.cpp:149:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<vc.size();j++)
~^~~~~~~~~~
oneway.cpp:152:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(r=0;r<q[x].size();r++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7808 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7808 KB |
Output is correct |
| 3 |
Correct |
8 ms |
7936 KB |
Output is correct |
| 4 |
Correct |
8 ms |
8064 KB |
Output is correct |
| 5 |
Correct |
8 ms |
8064 KB |
Output is correct |
| 6 |
Correct |
8 ms |
7936 KB |
Output is correct |
| 7 |
Correct |
9 ms |
8064 KB |
Output is correct |
| 8 |
Correct |
9 ms |
8064 KB |
Output is correct |
| 9 |
Runtime error |
485 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7808 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7808 KB |
Output is correct |
| 3 |
Correct |
8 ms |
7936 KB |
Output is correct |
| 4 |
Correct |
8 ms |
8064 KB |
Output is correct |
| 5 |
Correct |
8 ms |
8064 KB |
Output is correct |
| 6 |
Correct |
8 ms |
7936 KB |
Output is correct |
| 7 |
Correct |
9 ms |
8064 KB |
Output is correct |
| 8 |
Correct |
9 ms |
8064 KB |
Output is correct |
| 9 |
Runtime error |
485 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7808 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7808 KB |
Output is correct |
| 3 |
Correct |
8 ms |
7936 KB |
Output is correct |
| 4 |
Correct |
8 ms |
8064 KB |
Output is correct |
| 5 |
Correct |
8 ms |
8064 KB |
Output is correct |
| 6 |
Correct |
8 ms |
7936 KB |
Output is correct |
| 7 |
Correct |
9 ms |
8064 KB |
Output is correct |
| 8 |
Correct |
9 ms |
8064 KB |
Output is correct |
| 9 |
Runtime error |
485 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Halted |
0 ms |
0 KB |
- |
