#include <bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
using namespace std;
const int N=100001,lg=19;
int tim=0;
int sp[lg][N];
vector<int> adj[N],tin(N),tout(N),low(N),vis(N);
map<int,int> up[N],down[N];
map<pii,int> m,s;
map<pii,int> cnt;
bool SET(int a, int b){
if(cnt[mp(a,b)]==1) s[mp(a,b)]=s[mp(b,a)]=1;
return 1;
}
bool is_bridge(int a,int b){return s[mp(a,b)]; }
void dfs(int a, int p){
vis[a]=1;
sp[0][a]=p;
for(int i=1;i<lg;i++)
if(sp[i-1][a]!=-1)
sp[i][a]=sp[i-1][sp[i-1][a]];
tin[a]=++tim,low[a]=tim;
for(int&x:adj[a]){
if(x==p) continue;
if(vis[x])
low[a]=min(low[a],tin[x]);
else{
dfs(x,a);
low[a]=min(low[a],low[x]);
if(low[x]>tin[a]) SET(x,a);
}
}
tout[a]=++tim;
return ;
}
int is_ancestor(int a, int b){
return (tin[a]<=tin[b]&&tout[b]<=tout[a]);
}
int lca(int a, int b){
if(is_ancestor(a,b)) return a;
for(int i=lg-1;i>-1;--i)
if(sp[i][a]!=-1&&!is_ancestor(sp[i][a],b))
a=sp[i][a];
return sp[0][a];
}
int blca(int a, int b){
if(is_ancestor(a,b)) return -1;
for(int i=lg-1;i>-1;--i)
if(sp[i][a]!=-1&&!is_ancestor(sp[i][a],b))
a=sp[i][a];
return a;
}
void go(int a, int p,int dcnt,int ucnt){
dcnt+=down[a][0];
ucnt+=up[a][0];
vis[a]=0;
//cout<<dcnt<<" "<<ucnt<<" "<<a<<endl;
for(int&x:adj[a]){
if(vis[x]){
dcnt+=down[a][x];
ucnt+=up[a][x];
if(dcnt&&ucnt){}
else if(dcnt||ucnt){
if(dcnt){
m[mp(a,x)]=1;
m[mp(x,a)]=-1;
}
else{
m[mp(a,x)]=-1;
m[mp(x,a)]=1;
}
}
go(x,a,dcnt,ucnt);
dcnt-=down[a][x];
ucnt-=up[a][x];
}
}
dcnt+=down[a][0];
ucnt+=up[a][0];
}
int main(){
for(int i=0;i<lg;i++) for(int j=0;j<N;j++) sp[i][j]=-1;
int n,meme;
cin>>n>>meme;
vector<pii> ed;
while(meme--){
int a,b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
cnt[mp(a,b)]++;
cnt[mp(b,a)]++;
ed.push_back(mp(a,b));
}
for(int i=1;i<=n;i++)
if(!vis[i])
dfs(i,-1);
int q;
cin>>q;
vector<int> path;
function<bool(int,int)> launch=[&](int a, int b){
vis[a]=0;
path.push_back(a);
if(a==b) return 1;
for(int&x:adj[a])
if(vis[x]&&launch(x,b))
return 1;
path.pop_back();
return 0;
};
while(q--){
int a,b;
cin>>a>>b;
/*for(int i=1;i<=n;i++) vis[i]=1;
path.clear();
launch(a,b);
for(int i=0;i+1<path.size();i++){
m[mp(path[i],path[i+1])]=1;
m[mp(path[i+1],path[i])]=-1;
}*/
int lc=lca(a,b) ;
if(lc!=a){
up[lc][blca(a,b)]++;
up[a][0]--;
}
if(lc!=b){
down[lc][blca(b,a)]++;
down[b][0]--;
}
}
for(int i=1;i<=n;i++)
if(vis[i])
go(i,-1,0,0);
for(pii&x:ed){
if(x.F!=x.S&&is_bridge(x.F,x.S)){
if(m[x]==1)cout<<"R";
else if(m[x]==-1)cout<<"L";
else cout<<"B";
}
else cout<<"B";
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
20948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
20948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
20948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
