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