#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,p,bio[100005],d[100005],t=1,lo[100005],parent[100005],depth[100005],par2[25][100005],arr[100005],ind[100005];
vector <int> v[100005];
vector <pair<int,int> > v2;
vector <pair<int,int> > v3;
vector <pair<int,int> > p1;
map <pair<int,int>,int> m1;
string sol;
int find_par(int x) {
if(x==parent[x]) return x;
int par=find_par(parent[x]);
parent[x]=par;
return par;
}
void spoji(int x,int y) {
if(x>y) swap(x,y);
//cout << x << " " << y << "\n";
x=find_par(x);
y=find_par(y);
//cout << x << " " << y << "\n";
if(x==y) return;
if(depth[x]==depth[y]) depth[x]+=1;
if(depth[x]>depth[y]) parent[y]=x;
else parent[x]=y;
}
int dfs(int x,int par) {
bio[x]=1;
d[x]=t;
t+=1;
int ret=1e9;
for(int i=0;i<v[x].size();i++) {
if(v[x][i]==par) continue;
if(bio[v[x][i]]) {
//sol[abs(m1[make_pair(x,v[x][i])])-1]='B';
ret=min(ret,d[v[x][i]]);
spoji(x,v[x][i]);
}
else {
ret=min(ret,dfs(v[x][i],x));
if(d[x]<lo[v[x][i]]) {
v3.push_back(make_pair(min(x,v[x][i]),max(x,v[x][i])));
sol[abs(m1[make_pair(x,v[x][i])])-1]=' ';
}
else {
//cout << "abc " << x << " " << v[x][i] << "\n";
spoji(x,v[x][i]);
//sol[abs(m1[make_pair(x,v[x][i])])-1]='B';
}
}
}
lo[x]=ret;
return ret;
}
void dfs2(int x,int par,int d1) {
par2[0][x]=par;
depth[x]=d1;
for(int i=0;i<v[x].size();i++) {
if(v[x][i]==par) continue;
dfs2(v[x][i],x,d1+1);
}
}
int lca(int a,int b) {
if(depth[a]<depth[b]) swap(a,b);
for(int i=20;i>=0;i--) {
if((depth[a]-depth[b]) & (1 << i)) a=par2[i][a];
}
if(a==b) return a;
for(int i=20;i>=0;i--) {
if(par2[i][a]==par2[i][b]) continue;
a=par2[i][a];
b=par2[i][b];
}
return par2[0][a];
}
int dfs3(int x,int par) {
int ret=arr[x];
for(int i=0;i<v[x].size();i++) {
if(v[x][i]==par) continue;
ret+=dfs3(v[x][i],x);
}
//cout << x << " " << ret << " " << m1[make_pair(x,par)] << "\n";
if(x) {
if(ret==0 && sol[abs(m1[make_pair(x,par)])-1]!='L' && sol[abs(m1[make_pair(x,par)])-1]!='R') sol[abs(m1[make_pair(x,par)])-1]='B';
else if(ret==0) return ret;
else if(ret<0) {
if(m1[make_pair(x,par)]>0) sol[m1[make_pair(x,par)]-1]='R';
else sol[-m1[make_pair(x,par)]-1]='L';
}
else {
//cout << x << " " << par << " " << ret << " " << m1[make_pair(x,par)] << "\n";
if(m1[make_pair(x,par)]<0) sol[-m1[make_pair(x,par)]-1]='R';
else sol[m1[make_pair(x,par)]-1]='L';
}
}
return ret;
}
int main()
{
cin >> n >> m;
v2.clear();
v3.clear();
for(int i=0;i<n;i++) {
depth[i]=1;
parent[i]=i;
}
for(int j=0;j<m;j++) {
sol+='B';
int a,b;
cin >> a >> b;
m1[make_pair(a-1,b-1)]=j+1;
m1[make_pair(b-1,a-1)]=-j-1;
v2.push_back(make_pair(a-1,b-1));
v[a-1].push_back(b-1);
v[b-1].push_back(a-1);
}
cin >> p;
for(int i=0;i<p;i++) {
int a,b;
cin >> a >> b;
p1.push_back(make_pair(a-1,b-1));
}
dfs(0,-1);
/*for(int i=0;i<v3.size();i++) {
cout << v3[i].first << " " << v3[i].second << "\n";
}*/
for(int i=0;i<n;i++) {
v[i].clear();
}
for(int i=0;i<m;i++) {
if(find_par(v2[i].first)==find_par(v2[i].second)) continue;
v[find_par(v2[i].first)].push_back(find_par(v2[i].second));
v[find_par(v2[i].second)].push_back(find_par(v2[i].first));
m1[make_pair(find_par(v2[i].first),find_par(v2[i].second))]=i+1;
m1[make_pair(find_par(v2[i].second),find_par(v2[i].first))]=-i-1;
ind[v2[i].first]=find_par(v2[i].first);
ind[v2[i].second]=find_par(v2[i].second);
}
/*for(int i=0;i<n;i++) {
cout << ind[i] << " ";
}
cout << "\n";*/
memset(depth,0,sizeof(depth));
dfs2(0,-1,0);
for(int i=1;i<20;i++) {
for(int j=0;j<n;j++) {
par2[i][j]=par2[i-1][par2[i-1][j]];
}
}
for(int i=0;i<p;i++) {
arr[ind[p1[i].first]]-=1;
arr[lca(ind[p1[i].first],ind[p1[i].second])]+=1;
//cout << ind[p1[i].first] << " " << ind[p1[i].second] << " " << lca(ind[p1[i].first],ind[p1[i].second]) << "\n";
}
dfs3(0,-1);
//cout << sol << "\n";
memset(arr,0,sizeof(arr));
for(int i=0;i<p;i++) {
arr[ind[p1[i].second]]+=1;
arr[lca(ind[p1[i].first],ind[p1[i].second])]-=1;
//cout << p1[i].first << " " << p1[i].second << " " << lca(p1[i].first,p1[i].second) << "\n";
}
dfs3(0,-1);
cout << sol;
return 0;
}
Compilation message
oneway.cpp: In function 'int dfs(int, int)':
oneway.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++) {
~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int, int)':
oneway.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++) {
~^~~~~~~~~~~~
oneway.cpp: In function 'int dfs3(int, int)':
oneway.cpp:84:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++) {
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
3580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
3580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
3580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
