2022 星战 · 方案一重建判定

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 1858 字

n 点 m 条单向边（虫洞）

2022
计数

正文

// CSP-S 2022 复赛 T3 · 星战（方案一：每次询问重建判定，部分分）
// 原题：https://oj.yecheng.tv/p/CSPS2022C
// 题意：n 点 m 条单向边（虫洞）。四类事件：
//       1 u v：破坏边 u→v（该边失效）；2 u v：修复该边；
//       3 u：破坏 u 的全部出边；4 u：恢复 u 的全部出边。
//       每次事件后问：是否存在"从每个点出发沿虫洞走都恰好……"
//       —— 判定条件：每个点的出边数恰好为 1（这样从任意点出发
//       永远有唯一去路，题面口径）。
// 思路（暴力）：
//   维护边状态数组；每次询问后重扫所有点统计出度（邻接表过滤失效边）
//   判定是否全为 1。事件数与边数小（测试点 1~8）可过。
// 复杂度：O(q · m)。
// 易错点：
//   1. 边有"破坏/修复"两个状态位，不是删除；
//   2. 类型 3/4 是批量操作，注意与 1/2 的叠加关系；
//   3. 出度判定 = 恰好 1，不是至少 1。
#include <cstdio>
#include <vector>
using namespace std;

int n, m, q;
int eu[500005], ev[500005];
bool broken[500005];
vector<int> out_[500005];              // 点的出边编号

int outDeg(int u) {
    int c = 0;
    for (int e : out_[u]) if (!broken[e]) c++;
    return c;
}

int main() {
    freopen("galaxy.in", "r", stdin);
    freopen("galaxy.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &eu[i], &ev[i]);
        out_[eu[i]].push_back(i);
    }
    scanf("%d", &q);
    while (q--) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int u, v;
            scanf("%d%d", &u, &v);
            for (int e : out_[u])
                if (ev[e] == v) { broken[e] = true; break; }
        } else if (t == 2) {
            int u, v;
            scanf("%d%d", &u, &v);
            for (int e : out_[u])
                if (ev[e] == v) { broken[e] = false; break; }
        } else if (t == 3) {
            int u;
            scanf("%d", &u);
            for (int e : out_[u]) broken[e] = true;
        } else {
            int u;
            scanf("%d", &u);
            for (int e : out_[u]) broken[e] = false;
        }
        bool ok = true;
        for (int u = 1; u <= n && ok; u++)
            if (outDeg(u) != 1) ok = false;
        printf(ok ? "YES\n" : "NO\n");
    }
    return 0;
}

2022 星战 · 方案一 重建判定

正文

CSP-S 标程 · 复赛真题的其它内容

2022 星战 · 方案一重建判定