40pts AC#1#3#5#8求助

#define WANT_LDEBUG
#ifdef LOCAL
#include "D:/C++/include/all.h"
#else
#include <bits/stdc++.h>
#define ldebug(...)
#define cpp_version_ __cplusplus
#define REP(i, a, b) for (int i = a; i < (b); ++i)
#define RREP(i, a, b) for (int i = a; i > (b); --i)
#define FOR(i, a, b) for (int i = a; i <= (b); ++i)
#define RFOR(i, a, b) for (int i = a; i >= (b); --i)
#define REPK(i, a, b, k) for (int i = a; i < (b); i += k)
#define RREPK(i, a, b, k) for (int i = a; i > (b); i -= k)
#define FORK(i, a, b, k) for (int i = a; i <= (b); i += k)
#define RFORK(i, a, b, k) for (int i = a; i >= (b); i -= k)
using bool_t = signed char;
using u32 = unsigned int;
using i64 = long long;
using i128 = __int128;
using u64 = unsigned long long;
using f64 = double;
#define fast_io()                                                              \
    std::ios::sync_with_stdio(false);                                          \
    std::cin.tie(nullptr)
template <typename T, typename U> bool ckmax(T &a, const U& b) {
    return a < b && (a = b, true);
}
template <typename T, typename U> bool ckmin(T &a, const U& b) {
    return b < a && (a = b, true);
}
#endif
using namespace std;

constexpr int BLOCK = 1.5e4;
using B = bitset<BLOCK>;
int T, N, M;
struct predict_t {
    char o;
    int t, x, y;
};
vector<predict_t> predicts;
vector<set<int>> appear_times; //< 第i个人出现过的事件的所有时刻
int v_cnt;
map<pair<int, int>, array<int, 2>> id; //< id[{x, t}][0/1]: x 在时刻 t 死/活 的节点

vector<vector<int>> graph;
vector<int> deg, tmp_deg;
vector<B> f;

vector<bool_t> must_die;
vector<int> answer;

/**
 * @note 建反图，加反向边
 */
#ifdef LOCAL
ofstream fout("out.txt");
#endif
void add_edge(int u, int v) {
#ifdef DEBUG
    assert(0 <= u && u < v_cnt && 0 <= v && v < v_cnt);
#endif
#ifdef LOCAL
    fout << u << ' ' << v << '\n';
#endif
    graph[v].push_back(u);
    ++deg[u];
}
/**
 * @brief 初始化person在time时刻的生与死节点
 */
void init_node(int person, int time) {
    if (!appear_times[person].contains(time)) {
        int u = v_cnt++;
        int v = v_cnt++;
        ldebug("id[<{}, {}>] = [{}, {}]\n", person, time, u, v);
        graph.resize(v_cnt);
        deg.resize(v_cnt, 0);
        id[make_pair(person, time)] = array<int, 2>{{u, v}};
        appear_times[person].insert(time);
    }
}
void topo_sort() {
    static queue<int> q;
    REP(i, 0, v_cnt) {
        if (!tmp_deg[i]) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : graph[u]) {
            f[v] |= f[u];
            if (!--tmp_deg[v]) {
                q.push(v);
            }
        }
    }
}
void solve() {
    cin >> T >> N >> M;
    appear_times.resize(N);
    predicts.resize(M);
    for (auto& pred : predicts) {
        cin >> pred.o >> pred.t >> pred.x >> pred.y;
        --pred.x;
        --pred.y;
        init_node(pred.x, pred.t);
        if (pred.o == '0') {
            assert(pred.t + 1 <= T);
            init_node(pred.y, pred.t + 1);
            add_edge(id[make_pair(pred.x, pred.t)][0], id[make_pair(pred.y, pred.t + 1)][0]);
            add_edge(id[make_pair(pred.y, pred.t + 1)][1], id[make_pair(pred.x, pred.t)][1]);
        } else {
            init_node(pred.y, pred.t);
            add_edge(id[make_pair(pred.x, pred.t)][1], id[make_pair(pred.y, pred.t)][0]);
            add_edge(id[make_pair(pred.y, pred.t)][1], id[make_pair(pred.x, pred.t)][0]);
        }
    }
    REP(i, 0, N) {
        init_node(i, T);
        for (auto pre = appear_times[i].begin(), thi = next(pre); thi != appear_times[i].end(); pre = thi++) {
            add_edge(id[make_pair(i, *pre)][0], id[make_pair(i, *thi)][0]);
            add_edge(id[make_pair(i, *thi)][1], id[make_pair(i, *pre)][1]);
        }
    }
    f.resize(v_cnt);
    must_die.assign(N, false);
    answer.assign(N, N - 1);
    for (int l = 0, r; l < N; l = r) {
        tmp_deg = deg;
        r = min(N, l + BLOCK);
        for (auto &b : f) {
            b.reset();
        }
        //! 设置死亡状态为1
        REP(i, l, r) {
            f[id[make_pair(i, T)][0]].set(i - l);
        }
        topo_sort();
        REP(i, l, r) {
            if (f[id[make_pair(i, T)][1]].test(i - l)) {
                must_die[i] = true;
            }
        }
        REP(i, 0, N) {
            answer[i] -= f[id[make_pair(i, T)][1]].count();
        }
    }
    int must_die_cnt = ranges::count(must_die, true);
    REP(i, 0, N) {
        answer[i] -= must_die_cnt;
        if (must_die[i]) {
            answer[i] = 0;
        }
        cout << answer[i] << " \n"[i == N - 1];
    }
}
int main() {
    fast_io();
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
#ifdef DEBUgraph
        cerr << endl;
#endif
    }
    return 0;
}