【LOJ3101】「JSOI2019」精準預測

【題目連結】

• 點選打開連結

【思路要點】

• 顯然有 2 − s a t 2-sat 2−sat 建圖，注意到隻有緻死預測，且難兄難弟型預測存在時間先後關系，所建出的圖應當不存在環。
• 記 l i v e i , d e a d i live_i,dead_i livei​,deadi​ 分别表示 T + 1 T+1 T+1 時刻時表示 i i i 生/死的變量。

• 由于隻有緻死預測，當且僅當以下全部條件成立， L i v e ( i , j ) = 1 Live(i,j)=1 Live(i,j)=1 ：

  ( 1 ) (1) (1) 、 l i v e i live_i livei​ 不能到達 d e a d i dead_i deadi​ 。

  ( 2 ) (2) (2) 、 l i v e j live_j livej​ 不能到達 d e a d j dead_j deadj​ 。

  ( 3 ) (3) (3) 、 l i v e i live_i livei​ 不能到達 d e a d j dead_j deadj​ 。

• 用 b i t s e t bitset bitset 優化暴力即可，為解決空間過大的問題，可以将 N N N 個 d e a d i dead_i deadi​ 分若幹批處理。
• 時間複雜度 O ( N M ω ) O(\frac{NM}{\omega}) O(ωNM​) ，其中 ω = 64 \omega=64 ω=64 。

【代碼】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 5;
const int MAXM = 3e5 + 5;
const int block = 4096;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
set <int> timer[MAXN]; map <int, int> home[MAXN][2]; // 0 : Live, 1 : Dead
int T, n, m, tot, live[MAXN], dead[MAXN], key[MAXM];
int c[MAXM], x[MAXM], y[MAXM], t[MAXM];
bool vis[MAXM]; int bench, ans[MAXN];
bitset <block> f[MAXM]; bitset <MAXN> death;
vector <int> a[MAXM];
void work(int pos) {
	if (vis[pos]) return;
	vis[pos] = true, f[pos].reset();
	if (key[pos] >= bench && key[pos] < bench + block) f[pos].set(key[pos] - bench);
	for (auto x : a[pos]) {
		work(x);
		f[pos] |= f[x];
	}
}
int main() {
	read(T), read(n), read(m);
	for (int i = 1; i <= n; i++)
		timer[i].insert(T + 1);
	for (int i = 1; i <= m; i++) {
		read(c[i]), read(t[i]), read(x[i]), read(y[i]);
		timer[x[i]].insert(t[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (auto x : timer[i]) {
			home[i][0][x] = ++tot;
			home[i][1][x] = ++tot;
		}
		int last = 0;
		for (auto x : timer[i]) {
			if (last) {
				a[home[i][0][x]].push_back(home[i][0][last]);
				a[home[i][1][last]].push_back(home[i][1][x]);
			}
			last = x;
		}
	}
	for (int i = 1; i <= m; i++) {
		if (c[i] == 0) {
			int dest = *timer[y[i]].upper_bound(t[i]);
			a[home[x[i]][1][t[i]]].push_back(home[y[i]][1][dest]);
			a[home[y[i]][0][dest]].push_back(home[x[i]][0][t[i]]);
		} else {
			int dest = *timer[y[i]].lower_bound(t[i]);
			a[home[x[i]][0][t[i]]].push_back(home[y[i]][1][dest]);
			a[home[y[i]][0][dest]].push_back(home[x[i]][1][t[i]]);
		}
	}
	for (int i = 1; i <= n; i++) {
		live[i] = home[i][0][T + 1];
		dead[i] = home[i][1][T + 1];
		key[dead[i]] = i;
	}
	for (int p = 1; p <= n; p += block) {
		int q = min(p + block - 1, n); bench = p;
		memset(vis, false, sizeof(vis));
		for (int i = 1; i <= n; i++)
			work(live[i]);
		bitset <block> curr; curr.reset();
		for (int i = p; i <= q; i++)
			if (f[live[i]][i - bench]) {
				death.set(i);
				curr.set(i - bench);
			}
		int len = q - p + 1;
		for (int i = 1; i <= n; i++)
			ans[i] += len - (curr | f[live[i]]).count();
	}
	for (int i = 1; i <= n; i++)
		if (death[i]) printf("0 ");
		else printf("%d ", ans[i] - 1);
	return 0;
}