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