比赛 NOIP2025模拟赛2 评测结果 WWWWWAAAWWWWWWWWWWWWWWAWW
题目名称 道路改造 最终得分 16
用户昵称 徐诗畅 运行时间 1.583 s
代码语言 C++ 内存使用 16.26 MiB
提交时间 2025-11-25 11:20:49
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,p,head[N],cnt=1;
struct edg{int u,v;}ed[N];
struct edge{int v,nex,id;}e[N];
void addedge(int u,int v,int id){
	e[++cnt].v=v;
	e[cnt].nex=head[u];
	e[cnt].id=id;
	head[u]=cnt;
}
int dfn[N],low[N],num,scn,sc[N];
stack<int> st;
void dfs(int u,int E){
	dfn[u]=low[u]=++num;
	st.push(u);
	for(int i = head[u];i;i=e[i].nex){
		int v=e[i].v;
		if(i==E||i==(E^1)) continue;
		if(!dfn[v]){
			dfs(v,i);
			low[u]=min(low[u],low[v]);
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		scn++; int t;
		do{
			t=st.top(); st.pop();
			sc[t]=scn;
		}while(t!=u);
	}
}
struct node{int v,yu,yv,id;};
vector<node> g[N];
int up[N],dow[N];
int ans[N],fa[N],top[N],deep[N],siz[N],son[N];
void dfs1(int u,int f){
	fa[u]=f; siz[u]=1; deep[u]=deep[f]+1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].v; if(v==f) continue;
		dfs1(v,u); siz[u]+=siz[v];
		if(siz[v]>siz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int tp){
	top[u]=tp;
	if(!son[u]) return;
	dfs2(son[u],tp);
	for(int i = 0;i<g[u].size();i++){
		int v=g[u][i].v; if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
void dfs3(int u,int f){
	for(int i = 0;i<g[u].size();i++){
		int v=g[u][i].v; if(v==f) continue;
		dfs3(v,u); 
		up[u]+=up[v]; dow[u]+=dow[v];
	}
	for(int i = 0;i<g[u].size();i++){
		int v=g[u][i].v;
		if(up[u]){
			int id=g[u][i].id;
			if(ed[id].v==g[u][i].yu) ans[id]=1;
			else ans[id]=2;
		}
		if(dow[u]){
			int id=g[u][i].id;
			if(ed[id].u==g[u][i].yu) ans[id]=1;
			else ans[id]=2;
		}	
	}
}
int LCA(int u,int v){
	while(top[u]!=top[v]){
		if(deep[top[u]]<deep[top[v]]) swap(u,v);
		u=fa[top[u]];
	}
	if(deep[u]<deep[v]) return u; return v;
}
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",&ed[i].u,&ed[i].v);
		addedge(ed[i].u,ed[i].v,i);
		addedge(ed[i].v,ed[i].u,i);
	}
	for(int i = 1;i<=n;i++)
	if(!dfn[i]) dfs(i,0);
	for(int u = 1;u<=n;u++){
		for(int i = head[u];i;i=e[i].nex){
			int v=e[i].v;
			if(sc[u]!=sc[v]){
				g[sc[u]].push_back({sc[v],u,v,e[i].id});
			}
		}
	}
	dfs1(sc[1],0);  dfs2(sc[1],sc[1]); 
	scanf("%d",&p);
	while(p--){
		int u,v; scanf("%d%d",&u,&v);
		int lca=LCA(sc[u],sc[v]);
		up[sc[u]]++; up[lca]--;
		dow[sc[v]]++; dow[lca]--;
	}
	dfs3(sc[1],0);
	for(int i = 1;i<=m;i++)
	if(ans[i]==1) cout<<"L";
	else if(ans[i]==2) cout<<"R";
	else cout<<"B";
	return 0;
}