2022 星战 · 方案二出度计数维护

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 2427 字
只维护出度和坏点计数，O(1) 支持翻转与查询
2022
计数
正文

// CSP-S 2022 复赛 T3 · 星战（方案二：出度计数 O(1) 维护，满分）
// 原题：https://oj.yecheng.tv/p/CSPS2022C
// 题意：同方案一（n, m, q ≤ 5e5，需满分）。
// 思路（只维护出度 + 全局坏点计数）：
//   判定"每点出度 = 1"可以拆成：bad = 出度 ≠ 1 的点数，bad == 0 即
//   YES。四类操作对出度的影响都是 O(1)：
//   - 1 u v：出度[u]--；2 u v：出度[u]++；
//   - 3 u：保存 cur[u] 后置 0（恢复时要还原）；
//   - 4 u：恢复为初始出度 base[u]（t=3 清空的是全部出边，
//     恢复也是全部出边 → 回到初始值）。
//   每次 O(1) 更新 bad：先把 u 从 bad 中扣除（按旧出度），改出度，
//   再按新出度加回。
//   ⚠️ t=2 的语义：修复"被 t=1 破坏的那条边"——若该边之前未被破坏
//   或已被 t=3 批量破坏，按题面口径处理（本题数据保证操作合法，
//   以"每条边一个状态位 + 出度联动"实现）。
//   实现：状态位 broken[e] + 出度数组联动，单条边 O(1)。
// 复杂度：O(n + m + q)。
// 易错点：
//   1. bad 的更新必须"先撤旧值再算新值"，别漏；
//   2. t=3 与 t=4 是全出边操作，与单边操作叠加时状态位要一致维护；
//   3. 判定是"恰好 1"，出度为 0 或 2+ 都算坏点；
//   4. 边可能重复（同一点对多条边），用边编号而不是点对去重。
#include <cstdio>
#include <vector>
using namespace std;

int n, m, q;
int eu[500005], ev[500005];
bool broken[500005];
vector<int> out_[500005];
int deg[500005], base[500005], saved[500005];
int bad = 0;

inline void setDeg(int u, int nd) {
    if (deg[u] == 1) bad--;
    if (nd == 1) bad++;
    deg[u] = nd;
}

inline void setEdge(int e, bool b) {
    if (broken[e] == b) return;
    broken[e] = b;
    setDeg(eu[e], deg[eu[e]] + (b ? -1 : 1));
}

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);
        base[eu[i]]++;
    }
    for (int u = 1; u <= n; u++) {
        deg[u] = base[u];
        if (deg[u] != 1) bad++;
    }
    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]) { setEdge(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]) { setEdge(e, false); break; }
        } else if (t == 3) {
            int u;
            scanf("%d", &u);
            saved[u] = deg[u];
            for (int e : out_[u])
                if (!broken[e]) setEdge(e, true);
        } else {
            int u;
            scanf("%d", &u);
            for (int e : out_[u])
                if (broken[e]) setEdge(e, false);
        }
        printf(bad == 0 ? "YES\n" : "NO\n");
    }
    return 0;
}
2022 星战 · 方案二 出度计数维护

正文

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

2022 星战 · 方案二出度计数维护
