#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;
int n,m;
pii edge[100005];
vector<pii>adj[100005];
bool visited[100005];
bool self[100005];
int in[100005];
int low[100005];
int ptr=0;
bool bridge[100005];
int dir[100005];
int two[25][100005];
int d[100005];
void dfs(int index, int par){
//show(index,index);
in[index]=ptr;
low[index]=ptr;
ptr++;
visited[index]=true;
for(int x=0;x<20;x++){
two[x+1][index]=two[x][two[x][index]];
}
for(auto it:adj[index]){
if(!visited[it.first]){
two[0][it.first]=index;
d[it.first]=d[index]+1;
dfs(it.first,it.second);
if(low[it.first]>in[index]){
bridge[it.second]=true;
}
low[index]=min(low[index],low[it.first]);
}
else if(it.second!=par){
low[index]=min(low[index],in[it.first]);
}
}
}
int lca(int a, int b){
if(d[a]>d[b]) swap(a,b);
int diff=d[b]-d[a];
for(int x=0;x<20;x++){
if(diff&(1<<x)) b=two[x][b];
}
if(a==b) return a;
for(int x=19;x>=0;x--){
if(two[x][a]!=two[x][b]){
a=two[x][a];
b=two[x][b];
}
}
return two[0][a];
}
int up[100005];
int down[100005];
int visited2[100005];
pii storage[100005];
void dp(int index, int par){
visited2[index]=true;
storage[index]={up[index],down[index]};
for(auto it:adj[index]){
if(!visited2[it.first]){
dp(it.first,it.second);
storage[index].first=min(storage[index].first,storage[it.first].first);
storage[index].second=min(storage[index].second,storage[it.first].second);
}
}
if(par!=-1&&bridge[par]){
//show3(par,par,storage[index].first,storage[index].first,storage[index].second,storage[index].second);
//show(d[index],d[index]);
if(storage[index].first<d[index]){
dir[par]=index;
}
if(storage[index].second<d[index]){
dir[par]=-index;
}
}
}
void solve(){
cin >> n >> m;
int temp,temp2;
for(int x=0;x<m;x++){
cin >> temp >> temp2;
edge[x]={temp,temp2};
if(temp==temp2){
self[x]=true;
continue;
}
adj[temp].push_back({temp2,x});
adj[temp2].push_back({temp,x});
}
dfs(1,-1);
memset(dir,0,sizeof(dir));
for(int x=1;x<=n;x++){
up[x]=d[x];
down[x]=d[x];
}
int q;
cin >> q;
for(int x=0;x<q;x++){
cin >> temp >> temp2;
int hold=lca(temp,temp2);
//show(ancestor,hold);
if(hold==temp){
//down path
down[temp2]=min(down[temp2],d[temp]);
}
else if(hold==temp2){
//up path
up[temp]=min(up[temp],d[temp2]);
}
else{
//up down
up[temp]=min(up[temp],d[hold]);
down[temp2]=min(down[temp2],d[hold]);
}
}
dp(1,-1);
for(int x=0;x<m;x++){
if(self[x]){
cout << "B";
}
else if(!bridge[x]){
cout << "B";
}
else{
if(dir[x]==0){
cout << "B";
}
else if(dir[x]>0){
if(edge[x].first==dir[x]) cout << "R";
else cout << "L";
}
else{
if(edge[x].first==-dir[x]) cout << "L";
else cout << "R";
}
}
}
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("tribool.in", "r", stdin);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
21592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
21592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
21592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
