「JSOI2019」精准预测

「JSOI2019」精准预测

Problem

在 \(T\) 时刻内，有 \(m\) 个条件

• A 在 \(t\) 时刻死，B在 \(t+1\) 时刻死（如果A没死，那么将B活着）
• A在 \(t\) 时刻活，B在 \(t+1\) 时刻死（如果A死，那么将B活着）

求每个人在 \(T\) 时刻能与之共存的人有多少个

Thinking

一个朴素的做法是

对于每个人开 \(2T\) 个点表示每一时刻的生死状态

显然生死状态具有传递性（活着说明之前没死，死了说明不能再活）

但是发现会MLE

于是考虑用 set 维护关键的用到过的点

并且进行重新编号连边

Solution

与A共存的人数等于 n - 从A活着这个点出发能到达的人在 \(t\) 时刻死了的数量

于是考虑用DFS求解

发现可以用 bitset 优化可达点集

然后发现会MLE

于是考虑分块求解就可以了

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10, mxT = 1e6 + 10, K = 1e4 + 10, M = 1e5 + 10, V = (M + N) << 1;
int T, n, m, opt[M], t[M], x[M], y[M], alive[N], dead[N], id[V], ans[N];
map <int, int> idx[N][2];
set <int> use[N];
vector <int> e[V];
bitset <K> S[V]; bitset <V> mustdie, vis;
inline void ade (int u, int v) {e[u].emplace_back(v);}
void dfs(int u, int L, int R) {
    if (vis[u]) return;	
    vis.set(u), S[u].reset();
    if (L <= id[u] && id[u] <= R) S[u].set(id[u] - L);
    for (auto v : e[u]) dfs(v, L, R), S[u] |= S[v];
}
int main() {
    ios::sync_with_stdio(0);
    cin >> T >> n >> m;
    for (int i = 1; i <= m; i++) cin >> opt[i] >> t[i] >> x[i] >> y[i];
    for (int i = 1; i <= n; i++) use[i].emplace(T + 1);
    for (int i = 1; i <= m; i++) use[x[i]].emplace(t[i]);
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        for (auto t : use[i]) idx[i][0][t] = ++tot, idx[i][1][t] = ++tot;
        for (auto t = use[i].begin(); next(t) != use[i].end(); t++) ade(idx[i][0][*t], idx[i][0][*next(t)]), ade(idx[i][1][*next(t)], idx[i][1][*t]);
    }
    for (int i = 1; i <= m; i++) 
        if (!opt[i]) {
            int tim = *use[y[i]].upper_bound(t[i]);
            ade(idx[x[i]][0][t[i]], idx[y[i]][0][tim]), ade(idx[y[i]][1][tim], idx[x[i]][1][t[i]]);
        } else {
            int tim = *use[y[i]].lower_bound(t[i]);
            ade(idx[x[i]][1][t[i]], idx[y[i]][0][tim]), ade(idx[y[i]][1][tim], idx[x[i]][0][t[i]]);
        }
    for (int i = 1; i <= n; i++) alive[i] = idx[i][1][T + 1], id[dead[i] = idx[i][0][T + 1]] = i;
    int block = 1e4;
    for (int k = 0; k <= n / block; k++) {
        int L = k * block + 1, R = min(n, (k + 1) * block); vis.reset();
        // cout << L << ' ' << R << "\n";
        for (int i = 1; i <= n; i++) dfs(alive[i], L, R);
        bitset <K> res;
        for (int i = L; i <= R; i++) if (S[alive[i]][i - L]) mustdie.set(i), res.set(i - L);
        for (int i = 1; i <= n; i++) ans[i] += (R - L + 1) - (res | S[alive[i]]).count();
    }
    for (int i = 1; i <= n; i++) cout << (mustdie[i] ? 0 : ans[i] - 1) << ' ';
    return 0;
}