比赛 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;
}