#include <bits/stdc++.h>
using namespace std;
int n,m,a,b,t,i,who,k,q;
char ch[100001];
vector <int> v[100001];
vector <pair <int,pair <int,int> > > gr[100001];
bool fix[100001],block[100001],isbridge[100001];
int tin[100001],low[100001],parent[100001],in[100001],out[100001],aloup[100001],alodown[100001],A[100001],B[100001],p[100001][17];
map <pair<int,int>,int> mymap;
void dfsjust(int a,int c) {
parent[a]=c;
int i;
for (i=0;i<v[a].size();i++) {
if (parent[v[a][i]] && parent[v[a][i]]!=c && isbridge[mymap[{a,v[a][i]}]]) {
gr[c].push_back({parent[v[a][i]],{a,v[a][i]}});
gr[parent[v[a][i]]].push_back({c,{v[a][i],a}});
}
if (!parent[v[a][i]] && !isbridge[mymap[{a,v[a][i]}]])
dfsjust(v[a][i],c);
}
}
void justdfs(int a) {
fix[a]=1;
int i;
for (i=0;i<v[a].size();i++)
if (!fix[v[a][i]])
justdfs(v[a][i]);
}
void dfs(int a,int b) {
fix[a]=1;
tin[a]=low[a]=t++;
int i;
for (i=0;i<v[a].size();i++) {
if (v[a][i]==b)
continue;
if (fix[v[a][i]])
low[a]=min(low[a],tin[v[a][i]]);
else {
dfs(v[a][i],a);
low[a]=min(low[a],low[v[a][i]]);
if (low[v[a][i]]>tin[a])
isbridge[mymap[{a,v[a][i]}]]=1;
}
}
}
void go(int a,int b) {
in[a]=t++;
p[a][0]=b;
int i;
for (i=1;i<17;i++)
p[a][i]=p[p[a][i-1]][i-1];
for (i=0;i<gr[a].size();i++)
if (gr[a][i].first!=b)
go(gr[a][i].first,a);
out[a]=t++;
}
bool isp(int a,int b) {
if (in[a]<=in[b] && out[a]>=out[b])
return true;
return false;
}
int lca(int c,int b) {
int x=1,i;
for (i=16;i>=0;i--)
if (p[c][i] && !isp(p[c][i],b)) {
c=p[c][i];
x+=(1<<i);
}
return x;
}
void gogo(int a,int b) {
int i;
for (i=0;i<gr[a].size();i++)
if (gr[a][i].first!=b) {
if (aloup[gr[a][i].first] || alodown[gr[a][i].first]) {
int hey=mymap[{gr[a][i].second.first,gr[a][i].second.second}];
if (aloup[gr[a][i].first])
swap(A[hey],B[hey]);
if (gr[a][i].second.second==B[hey])
ch[hey]='R';
else
ch[hey]='L';
}
gogo(gr[a][i].first,a);
}
}
int goup(int a,int b) {
int i,x=0;
for (i=0;i<gr[a].size();i++)
if (gr[a][i].first!=b)
x=max(x,goup(gr[a][i].first,a));
return aloup[a]=max(aloup[a],x-1);
}
int godown(int a,int b) {
int i,x=0;
for (i=0;i<gr[a].size();i++)
if (gr[a][i].first!=b)
x=max(x,godown(gr[a][i].first,a));
return alodown[a]=max(alodown[a],x-1);
}
int main() {
cin>>n>>m;
for (i=1;i<=m;i++) {
ch[i]='B';
cin>>a>>b;
A[i]=a;B[i]=b;
if (a==b)
continue;
if (mymap[{a,b}])
block[mymap[{a,b}]]=block[mymap[{b,a}]]=1;
else {
v[a].push_back(b);
v[b].push_back(a);
mymap[{a,b}]=mymap[{b,a}]=i;
}
}
for (i=1;i<=n;i++) {
if (!fix[i])
justdfs(i);
else
continue;
if (who) {
v[who].push_back(i);
v[i].push_back(who);
}
else
who=i;
}
for (i=1;i<=n;i++)
fix[i]=0;
for (i=1;i<=n;i++)
if (!fix[i])
dfs(i,-1);
for (i=1;i<=n;i++)
if (!parent[i])
dfsjust(i,++k);
go(1,0);
cin>>q;
for (i=1;i<=q;i++) {
cin>>a>>b;
a=parent[a];
b=parent[b];
if (!isp(a,b))
aloup[a]=max(aloup[a],lca(a,b));
if (!isp(b,a))
alodown[b]=max(alodown[b],lca(b,a));
}
aloup[1]=goup(1,0);
alodown[1]=godown(1,0);
gogo(1,0);
for (i=1;i<=m;i++) {
if (block[mymap[{a,b}]])
ch[i]='B';
cout<<ch[i];
}
cout<<endl;
}
Compilation message
oneway.cpp: In function 'void dfsjust(int, int)':
oneway.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[a].size();i++) {
~^~~~~~~~~~~~
oneway.cpp: In function 'void justdfs(int)':
oneway.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[a].size();i++)
~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[a].size();i++) {
~^~~~~~~~~~~~
oneway.cpp: In function 'void go(int, int)':
oneway.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<gr[a].size();i++)
~^~~~~~~~~~~~~
oneway.cpp: In function 'void gogo(int, int)':
oneway.cpp:73:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<gr[a].size();i++)
~^~~~~~~~~~~~~
oneway.cpp: In function 'int goup(int, int)':
oneway.cpp:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<gr[a].size();i++)
~^~~~~~~~~~~~~
oneway.cpp: In function 'int godown(int, int)':
oneway.cpp:97:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<gr[a].size();i++)
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5368 KB |
Output is correct |
| 6 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 7 |
Correct |
9 ms |
5468 KB |
Output is correct |
| 8 |
Correct |
9 ms |
5368 KB |
Output is correct |
| 9 |
Incorrect |
8 ms |
5228 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5368 KB |
Output is correct |
| 6 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 7 |
Correct |
9 ms |
5468 KB |
Output is correct |
| 8 |
Correct |
9 ms |
5368 KB |
Output is correct |
| 9 |
Incorrect |
8 ms |
5228 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5368 KB |
Output is correct |
| 6 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 7 |
Correct |
9 ms |
5468 KB |
Output is correct |
| 8 |
Correct |
9 ms |
5368 KB |
Output is correct |
| 9 |
Incorrect |
8 ms |
5228 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
