#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define cd complex<double>
#define p_q priority_queue
using namespace std;
vector<vector<pair<int,int> > > e;
vector<int> dfn,low;
vector<int> ans;
vector<int> vis;
vector<int> tt;
int cnt=1,cc=1;
void dfs(int r,int f){
dfn[r]=low[r]=cnt;
cnt++;
if(f>0){
vis[f]=1;
}
for(auto h:e[r]){
if(vis[h.sc]){
continue;
}
if(dfn[h.fs]){
low[r]=min(low[r],dfn[h.fs]);
}
else{
dfs(h.fs,h.sc);
low[r]=min(low[r],low[h.fs]);
if(low[h.fs]==dfn[h.fs]){
ans[h.sc]=1;
}
}
}
}
void ftt(int r,int f){
tt[r]=cc;
for(auto h:e[r]){
if(tt[h.fs]){
continue;
}
if(ans[h.sc]==0){
ftt(h.fs,h.sc);
}
}
for(auto h:e[r]){
if(tt[h.fs]){
continue;
}
if(ans[h.sc]==1){
cc++;
ftt(h.fs,h.sc);
}
}
}
vector<int> kk;
vector<vector<pair<int,int> > > ff;
vector<int> deg;
vector<int> vis2;
void dfs3(int r,int f){
if(kk[r]!=0 && deg[r]==1){
vis2[r]=1;
for(auto h:ff[r]){
if(h.fs!=f){
ans[h.sc]=1;
deg[h.fs]--;
dfs3(h.fs,r);
}
}
}
}
vector<pair<int,int> > eg;
void dfs4(int r,int f){
for(auto h:ff[r]){
if(h.fs!=f){
if(r!=0){
if(eg[h.sc].sc==r){
ans[h.sc]=-1;
}
else{
ans[h.sc]=1;
}
}
dfs4(h.fs,r);
}
}
}
int main(){
AquA;
int n,m;
cin >> n >> m;
e.resize(n);
eg.resize(m);
for(int i=0;i<m;i++){
int a,b;
cin >> a >> b;
a--;
b--;
e[a].push_back({b,i});
e[b].push_back({a,i});
eg[i]={a,b};
}
dfn.resize(n);
low.resize(n);
ans.resize(m);
vis.resize(m);
for(int i=0;i<n;i++){
if(!dfn[i]){
dfs(i,-1);
}
}
tt.resize(n);
for(int i=0;i<n;i++){
if(!tt[i]){
ftt(i,-1);
}
}
ff.resize(cc+1);
deg.resize(cc+1);
vis2.resize(cc+1);
for(int i=0;i<n;i++){
for(auto h:e[i]){
if(tt[i]!=tt[h.fs]){
ff[tt[i]].push_back({tt[h.fs],h.sc});
ff[tt[h.fs]].push_back({tt[i],h.sc});
deg[tt[i]]++;
deg[tt[h.fs]]++;
}
}
}
int p;
cin >> p;
kk.resize(n);
for(int i=0;i<p;i++){
int a,b;
cin >> a >> b;
a--;
b--;
a=tt[a];
b=tt[b];
if(a==b){
continue;
}
kk[a]=1;
kk[b]=-1;
ff[0].push_back({a,-1});
}
for(int i=1;i<=cc;i++){
if(deg[i]==1){
dfs3(i,i);
}
}
dfs4(0,0);
for(int i=0;i<m;i++){
if(ans[i]==0){
cout << "B";
}
else if(ans[i]==1){
cout << "L";
}
else if(ans[i]==-1){
cout << "R";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
