#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,k,u[200000],fup[200000],tin[200000],timer;
vector<pair<int,int> > g[200000],br,tr[200000];
vector<pair<int,pair<int,int > > > cuc;
char pa[200000];
int sz[200000],par[2000000],uxx[200000],ux[200000],ind[200000],parent[200000][22],tiin[200000],tout[200000],pp[200000],h[200000];
void setcreate(int a)
{
sz[a]=1;
par[a]=a;
}
int findparent(int a)
{
if(par[a]==a)
return a;
return par[a]=findparent(par[a]);
}
void setunion(int a,int b)
{
a=findparent(a);
b=findparent(b);
if(a==b)
return;
if(sz[a]>=sz[b])
{
par[b]=a;
sz[a]+=sz[b];
}
if(sz[b]>sz[a])
{
par[a]=b;
sz[b]+=sz[a];
}
}
void dfs(int v,int p)
{
u[v]=1;
fup[v]=tin[v]=timer++;
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i].first;
int ham=g[v][i].second;
if(to==v)
{
pa[ham]='B';
continue;
}
if(p==to)
continue;
if(u[to]==1)
{
fup[v]=min(fup[v],tin[to]);
pa[ham]='B';
setunion(v,to);
}
else
{
dfs(to,v);
fup[v]=min(fup[v],fup[to]);
if(fup[to]>tin[v])
br.push_back(make_pair(v,i));
else
{
pa[ham]='B';
setunion(v,to);
}
}
}
}
void dfs1(int v,int p)
{
tiin[v]=timer++;
u[v]=1;
parent[v][0]=p;
for(int i=1;i<=20;i++)
parent[v][i]=parent[parent[v][i-1]][i-1];
for(int i=0;i<tr[v].size();i++)
{
int to=tr[v][i].first;
int ham=tr[v][i].second;
if(to==p)
continue;
pp[to]=ham;
h[to]=h[v]+1;
dfs1(to,v);
}
tout[v]=timer++;
}
bool upper (int a, int b) {
return tiin[a] <= tiin[b] && tout[a] >= tout[b];
}
int lca (int a, int b) {
if (upper (a, b)) return a;
if (upper (b, a)) return b;
for (int i=20; i>=0; --i)
if (! upper (parent[a][i], b))
a = parent[a][i];
return parent[a][0];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
uxx[i]=a;
g[a].push_back(make_pair(b,i));
g[b].push_back(make_pair(a,i));
}
for(int i=1;i<=n;i++)
setcreate(i);
for(int i=1;i<=n;i++)
{
if(u[i]==0)
dfs(i,0);
}
for(int i=1;i<=n;i++)
ind[i]=findparent(i);
for(int i=0;i<br.size();i++)
{
int a=br[i].first,b=g[a][br[i].second].first,ham=g[a][br[i].second].second;
uxx[ham]=ind[uxx[ham]];
tr[ind[a]].push_back(make_pair(ind[b],ham));
tr[ind[b]].push_back(make_pair(ind[a],ham));
}
for(int i=1;i<=n;i++)
u[ind[i]]=0;
timer=0;
for(int i=1;i<=n;i++)
{
if(u[ind[i]]==0)
dfs1(ind[i],ind[i]);
}
cin>>k;
for(int i=1;i<=k;i++)
{
int a,b;
cin>>a>>b;
a=ind[a];
b=ind[b];
if(a==b)
continue;
int c=lca(a,b);
cuc.push_back(make_pair(h[c],make_pair(a,b)));
}
sort(cuc.begin(),cuc.end());
for(int i=0;i<cuc.size();i++)
{
int a=cuc[i].second.first,b=cuc[i].second.second;
int c=lca(a,b);
int e=a;
while(e!=c)
{
int ee=parent[e][0];
if(pa[pp[e]]=='R' || pa[pp[e]]=='L')
break;
if(uxx[pp[e]]==e)
pa[pp[e]]='R';
else
pa[pp[e]]='L';
e=ee;
}
e=b;
while(e!=c)
{
int ee=parent[e][0];
if(pa[pp[e]]=='R' || pa[pp[e]]=='L')
break;
if(uxx[pp[e]]==e)
pa[pp[e]]='L';
else
pa[pp[e]]='R';
e=ee;
}
}
for(int i=1;i<=m;i++)
{
if(pa[i]==0)
pa[i]='B';
cout<<pa[i];
}
return 0;
}
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/
Compilation message
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs1(int, int)':
oneway.cpp:80:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<tr[v].size();i++)
~^~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:124:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<br.size();i++)
~^~~~~~~~~~
oneway.cpp:152:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<cuc.size();i++)
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9864 KB |
Output is correct |
| 3 |
Correct |
11 ms |
10104 KB |
Output is correct |
| 4 |
Correct |
12 ms |
10184 KB |
Output is correct |
| 5 |
Correct |
11 ms |
10208 KB |
Output is correct |
| 6 |
Correct |
15 ms |
10236 KB |
Output is correct |
| 7 |
Correct |
13 ms |
10428 KB |
Output is correct |
| 8 |
Correct |
11 ms |
10428 KB |
Output is correct |
| 9 |
Runtime error |
1312 ms |
263168 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 |
11 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9864 KB |
Output is correct |
| 3 |
Correct |
11 ms |
10104 KB |
Output is correct |
| 4 |
Correct |
12 ms |
10184 KB |
Output is correct |
| 5 |
Correct |
11 ms |
10208 KB |
Output is correct |
| 6 |
Correct |
15 ms |
10236 KB |
Output is correct |
| 7 |
Correct |
13 ms |
10428 KB |
Output is correct |
| 8 |
Correct |
11 ms |
10428 KB |
Output is correct |
| 9 |
Runtime error |
1312 ms |
263168 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 |
11 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9864 KB |
Output is correct |
| 3 |
Correct |
11 ms |
10104 KB |
Output is correct |
| 4 |
Correct |
12 ms |
10184 KB |
Output is correct |
| 5 |
Correct |
11 ms |
10208 KB |
Output is correct |
| 6 |
Correct |
15 ms |
10236 KB |
Output is correct |
| 7 |
Correct |
13 ms |
10428 KB |
Output is correct |
| 8 |
Correct |
11 ms |
10428 KB |
Output is correct |
| 9 |
Runtime error |
1312 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Halted |
0 ms |
0 KB |
- |
