比赛 NOIP2025模拟赛2 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称 道路改造 最终得分 100
用户昵称 淮淮清子 运行时间 1.194 s
代码语言 C++ 内存使用 9.62 MiB
提交时间 2025-11-25 12:26:25
显示代码纯文本
#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 100005;
int n, m, p;
int idu[MAXN], idv[MAXN];
struct Edge{
	int to, nxt, id;
} e[MAXN << 1];
int h[MAXN], tot;
void add(int x, int y, int id){
    e[++ tot] = {y, h[x], id};
    h[x] = tot;
}

struct NODE{
	int to, nxt;
}E[MAXN << 1];
int h2[MAXN], tot2;
void add2(int x, int y) {
    E[++ tot2] = {y, h2[x]};
    h2[x] = tot2;
}

int dfn[MAXN], low[MAXN], tim;
int stk[MAXN], top;
bool ins[MAXN];
int scc[MAXN], cnt;

int d[MAXN], ans[MAXN], dep[MAXN];

void tarjan(int u, int fe){
    dfn[u] = low[u] = ++ tim;
    stk[++ top] = u; ins[u] = 1;
    for(int i = h[u]; i; i = e[i].nxt){
        int v = e[i].to;
        if(e[i].id == fe) continue;
        if(!dfn[v]){
            tarjan(v, e[i].id);
            low[u] = min(low[u], low[v]);
        }
		else if (ins[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]){
        cnt ++;
        int v;
        do{
            v = stk[top --];
            ins[v] = 0;
            scc[v] = cnt;
        }while (u != v);
    }
}

void dfs(int u, int fa){
    dep[u] = dep[fa] + 1;
    for(int i = h2[u]; i; i = E[i].nxt){
        int v = E[i].to;
        if(v == fa) continue;
        dfs(v, u);
        ans[u] += ans[v];
    }
}

int main(){
    freopen("streetr.in", "r", stdin);
    freopen("streetr.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= m;i ++){
        int u, v; cin >> u >> v;
        idu[i] = u; idv[i] = v;
        add(u, v, i); add(v, u, i);
    }
    for(int i = 1;i <= n;i ++){
    	if(!dfn[i]){
    		tarjan(i, 0);
		}
	}
    for(int i = 1;i <= m;i ++){
        int u = scc[idu[i]], b = scc[idv[i]];
        if(u != b){
        	add2(u, b);
			add2(b, u);
		}
    }
    cin >> p;
    while(p --){
        int u, v; cin >> u >> v;
        u = scc[u], v = scc[v];
        d[u] ++, d[v] --;
    }
    memcpy(ans, d, sizeof d);
    for(int i = 1;i <= cnt;i ++){
    	if(!dep[i]){
    		dfs(i, 0);
		}
	}
    for(int i = 1;i <= m;i ++){
        int u = scc[idu[i]], v = scc[idv[i]];
        if(u == v){
        	cout << 'B';
		}
        else if(dep[u] > dep[v]){
        	cout << "RBL"[ans[u] > 0 ? 0 : (ans[u] == 0 ? 1 : 2)];
		}
        else{
        	cout << "LBR"[ans[v] > 0 ? 0 : (ans[v] == 0 ? 1 : 2)];
		}
    }
    cout << '\n';
    return 0;
}