#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=5e5+1;
vec<array<int,3>> g[N];
int in[N],out[N],tt=1,fup[N],up[N][20];
char clr[N];
bool is(int a,int b){
return in[a]<=in[b]&&out[a]>=out[b];
}
vec<array<int,3>> gr[N];
void dfs(int v,int p,int pr){
in[v]=fup[v]=tt++;
up[v][0]=pr;
for(int i=1;i<20;i++) up[v][i]=up[up[v][i-1]][i-1];
for(auto &z : g[v]){
if(z[1]==p) continue;
if(in[z[0]]){
umin(fup[v],in[z[0]]);
if(in[z[0]]<in[v])
cout<<"E! "<<v<<' '<<z[0]<<endl;
clr[z[1]]='B';
}
else{
// cout<<"E "<<v<<' '<<z[0]<<endl;
dfs(z[0],z[1],v);
gr[v].pb(z);
umin(fup[v],fup[z[0]]);
// cout<<"E "<<v<<' '<<z[0]<<' '<<in[v]<<' '<<fup[z[0]]<<endl;
if(fup[z[0]]<=in[v])
clr[z[1]]='B';
else
clr[z[1]]='.';
}
}
out[v]=tt-1;
}
int dp[N][2];
string fck="LR";
void dfs2(int v){
for(auto &z : gr[v]){
dfs2(z[0]);
for(int t=0;t<2;t++)
dp[v][t]+=dp[z[0]][t];
// cout<<dp[z[0]][0]<<' '<<
if(dp[z[0]][0] || dp[z[0]][1]){
if(clr[z[1]]=='B') continue;
if(dp[z[0]][0])
clr[z[1]]=fck[0^z[2]^1];
else
clr[z[1]]=fck[1^z[2]^1];
}
else clr[z[1]]='B';
}
}
int lca(int a,int b){
if(is(a,b)) return a;
for(int i=19;i>=0;i--){
if(!is(up[a][i],b))
a=up[a][i];
}
return up[a][0];
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int v,u;
cin>>v>>u;--v;--u;
g[v].pb({u,i,0});
g[u].pb({v,i,1});
}
vec<int>roots;
for(int i=0;i<n;i++){
if(!in[i])
roots.pb(i),dfs(i,-1,i);
}
int q;
cin>>q;
while(q--){
int v,u;
cin>>v>>u;--v;--u;
cerr<<"WO "<<v<<' '<<u<<' '<<lca(v,u)<<endl;
dp[v][1]++;
dp[u][0]++;
dp[lca(v,u)][0]--;
dp[lca(v,u)][1]--;
}
for(auto &z : roots)
dfs2(z);
for(int i=0;i<m;i++)
cout<<clr[i];
return 0;
}
/*
10 10 1
6 5
5 1
1 4
2 4
2 10
3 1
3 8
9 8
9 7
6 8
3 9 8
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
