| 比赛 |
NOIP2025模拟赛2 |
评测结果 |
AAAAAAAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
道路改造 |
最终得分 |
100 |
| 用户昵称 |
梦那边的美好TE |
运行时间 |
2.054 s |
| 代码语言 |
C++ |
内存使用 |
17.17 MiB |
| 提交时间 |
2025-11-25 12:22:55 |
显示代码纯文本
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int N=1e5+10;
const int M=5e5+10;
int n,m,ver[N],to[M],nxt[M],idx=1,id[M],tot,mk[M],chk[N];
int dcc,dfn[N],low[N],vis[N],from[N],fat[N],fath[N];
int dep[N],st[N][18],opt[N];
vector<int>G[N];
void add(int x,int y,int z){
to[++idx]=y,nxt[idx]=ver[x],ver[x]=idx,id[idx]=z;
}
void link(int x,int y){
G[x].push_back(y);
}
void tarjan(int u,int e){
dfn[u]=low[u]=++tot;
for(int i=ver[u];i;i=nxt[i]){
int v=to[i];
if(!dfn[v]){
tarjan(v,i);
if(low[v]>dfn[u]){
mk[i]=mk[i^1]=1;
}
low[u]=min(low[u],low[v]);
}else if((e^1)!=i){
low[u]=min(low[u],dfn[v]);
}
}
}
void dfs(int x){
vis[x]=1,from[x]=dcc;
for(int i=ver[x];i;i=nxt[i]){
int y=to[i];
if(!mk[i]&&!vis[y])dfs(y);
}
return;
}
void DFS(int x,int fa){
fat[x]=fa,chk[x]=1;
dep[x]=dep[fa]+1;
st[x][0]=fa;
for(int i=1;i<18;i++)st[x][i]=st[st[x][i-1]][i-1];
for(auto y:G[x]){
if(y==fa)continue;
DFS(y,x);
}
return;
}
int LCA(int a,int b){
if(dep[a]<dep[b])swap(a,b);
for(int i=17;i>=0;i--)if(dep[st[a][i]]>=dep[b])a=st[a][i];
if(a==b)return a;
for(int i=17;i>=0;i--)if(st[a][i]!=st[b][i])a=st[a][i],b=st[b][i];
return st[a][0];
}
int found(int x){
return fath[x]==x?x:fath[x]=found(fath[x]);
}
void change(int x,int y,int option){
while(1){
x=found(x);
if(dep[x]<=dep[y])break;
opt[x]=option;
fath[x]=found(fat[x]);
}
return;
}
int u[M],v[M];
int main(){
freopen("streetr.in","r",stdin);
freopen("streetr.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d %d",u+i,v+i);
add(u[i],v[i],i);
add(v[i],u[i],i);
}
for(int i=1;i<=n;i++)tarjan(i,0);
for(int i=1;i<=n;i++){
if(!vis[i]){
dcc++;
dfs(i);
}
}
for(int i=1;i<=m;i++){
if(from[u[i]]!=from[v[i]]){
link(from[u[i]],from[v[i]]);
link(from[v[i]],from[u[i]]);
}
}
for(int i=1;i<=n;i++)if(!chk[i])DFS(i,0);
int p,x,y,z;
for(int i=1;i<=dcc;i++)fath[i]=i;
scanf("%d",&p);
for(int i=1;i<=p;i++){
scanf("%d %d",&x,&y);
x=from[x],y=from[y];
if(x==y)continue;
z=LCA(x,y);
change(x,z,1);
change(y,z,2);
}
for(int i=1;i<=m;i++){
if(from[u[i]]==from[v[i]]){
printf("B");
}else{
int x=from[u[i]];
int y=from[v[i]];
if(fat[x]==y){
if(opt[x]==1){
printf("R");
}else if(opt[x]==2){
printf("L");
}else{
printf("B");
}
}else{
if(opt[y]==1){
printf("L");
}else if(opt[y]==2){
printf("R");
}else{
printf("B");
}
}
}
}
printf("\n");
return 0;
}