#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N=1e5+5;
const ll MOD=1e9+7;
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
ll n,m,q,x,y;
vector<ll> v[N];
pll ed[N];
ll ans[N];
ll depth[N],low[N],stk[N],now,vis[N],color[N],is_bridge[N];
void DFS(ll nd,ll par,ll par_edge){
vis[nd]=1;
stk[++now]=nd;
low[nd]=depth[nd]=depth[par]+1;
for(auto i:v[nd]){
if(i==par_edge)continue;
ll to=ed[i].X+ed[i].Y-nd;
if(vis[to]){
low[nd]=min(low[nd],depth[to]);
}else{
DFS(to,nd,i);
low[nd]=min(low[nd],low[to]);
}
}
if(low[nd]>=depth[nd]){
is_bridge[par_edge]=1;
while(stk[now]!=nd){
color[stk[now]]=nd;
--now;
}
color[stk[now--]]=nd;
}
}
ll ti,in[N],out[N],anc[N][20],pe[N];
void dfs(ll nd,ll pa,ll par_edge){
pe[nd]=par_edge;
anc[nd][0]=pa;
REP1(i,18)anc[nd][i]=anc[anc[nd][i-1]][i-1];
in[nd]=++ti;
for(ll i:v[nd]){
if(i==par_edge)continue;
ll to=(ed[i].X+ed[i].Y)-nd;
dfs(to,nd,i);
}
out[nd]=++ti;
}
bool is_anc(ll nda,ll ndb){
return (in[nda]<=in[ndb]&&out[nda]>=out[ndb]);
}
ll lca(ll nda,ll ndb){
if(is_anc(nda,ndb))return nda;
if(is_anc(ndb,nda))return ndb;
for(int i=18;i>=0;i--){
if(!anc[nda][i])continue;
if(!is_anc(anc[nda][i],ndb)){
nda=anc[nda][i];
}
}
return anc[nda][0];
}
ll fr(ll A,ll nd){//A is an ancestor of nd
for(int i=18;i>=0;i--){
if(!anc[nd][i])continue;
if(!is_anc(anc[nd][i],A))nd=anc[nd][i];
}
return nd;
}
ll u[N],d[N];
void build(ll nd,ll pa,ll par_edge){
for(auto i:v[nd]){
if(i==par_edge)continue;
ll to=(ed[i].X+ed[i].Y)-nd;
build(to,nd,i);
u[nd]+=u[to];
d[nd]+=d[to];
}
if(u[nd])ans[par_edge]=nd;
if(d[nd])ans[par_edge]=pa;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
//reset
//
cin>>n>>m;
REP1(i,m){
cin>>ed[i].X>>ed[i].Y;
v[ed[i].X].pb(i);
v[ed[i].Y].pb(i);
}
DFS(1,0,0);
REP1(i,n)v[i].clear();
REP1(i,m){
if(is_bridge[i]){
ed[i].X=color[ed[i].X];
ed[i].Y=color[ed[i].Y];
assert(ed[i].X!=ed[i].Y);
v[ed[i].X].pb(i);v[ed[i].Y].pb(i);
}
}
dfs(color[1],0,0);
cin>>q;
while(q--){
cin>>x>>y;
x=color[x];y=color[y];
if(x==y)continue;
ll L=lca(x,y);
if(L!=x){
++u[x];--u[L];
}
if(L!=y){
++d[y];--d[L];
}
}
build(color[1],0,0);
REP1(i,m){
if(is_bridge[i]){
cout<<(ans[i]==0?"B":(ans[i]==ed[i].X?"R":"L"));
}else{
cout<<"B";
}
if(i==m)cout<<"\n";
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
