LOJ#3101. 「JSOI2019」精准预测
设0是生，1是死，按2-sat连边那么第一种情况是\((t,x,1) \rightarrow (t + 1,y,1)\)，\((t + 1,y, 0) \rightarrow (t,x,0)\)
第二种情况是\((t,x,0) \rightarrow (t,y,1)\),\((t,y,0) \rightarrow(t,x,1)\)
然后\((t,x,0)\)往\((t - 1,x,0)\)连边，\((t,x,1)\)往\((t + 1,x,1)\)连边
发现我们显然可以忽略出度只有一个的点，最后只剩下\(2m + 2n\)个点
然后这是一张DAG，因为生的图是一张DAG，死的图是一张DAG，剩下的只有从生连到死的边
于是我们要求从\((T + 1,x,0)\)走到的\((T + 1,y,1)\)的个数，然后减去
同时我们还要给每个点减去一定会死的人
用bitset优化一下即可。。。
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define ba 47
#define MAXN 50005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
struct node {
int to,next;
}E[2000005];
struct predict {
int ty,t,x,y;
}pre[100005];
int T,N,M,Ncnt;
vector<int> tim[2][MAXN],pos[2][MAXN];
bitset<50005> reach[100005],all,res[50005];
int head[300005],sumE,deg[300005],rec[300005],dead[300005],live[300005];
vector<int> que,used;
int pu[300005],ans[50005];
void add(int u,int v) {
if(!v || !u) return;
E[++sumE].to = v;
E[sumE].next = head[u];
++deg[v];++rec[v];
head[u] = sumE;
}
int getid(int k,int x,int t) {
if(k == 0) {
int tar = upper_bound(tim[k][x].begin(),tim[k][x].end(),t) - tim[k][x].begin() - 1;
if(tar < 0) return 0;
return pos[k][x][tar];
}
else {
int tar = lower_bound(tim[k][x].begin(),tim[k][x].end(),t) - tim[k][x].begin();
return pos[k][x][tar];
}
}
void Init() {
read(T);read(N);read(M);
Ncnt = 0;
for(int i = 1 ; i <= N ; ++i) {tim[1][i].pb(T + 1);tim[0][i].pb(T + 1);}
for(int i = 1 ; i <= M ; ++i) {
read(pre[i].ty);read(pre[i].t);read(pre[i].x);read(pre[i].y);
if(pre[i].ty == 0) {
tim[1][pre[i].x].pb(pre[i].t);
tim[0][pre[i].y].pb(pre[i].t + 1);
}
else {
tim[0][pre[i].x].pb(pre[i].t);
tim[0][pre[i].y].pb(pre[i].t);
}
}
for(int i = 1 ; i <= N ; ++i) {
for(int k = 0 ; k < 2 ; ++k) {
sort(tim[k][i].begin(),tim[k][i].end());
tim[k][i].erase(unique(tim[k][i].begin(),tim[k][i].end()),tim[k][i].end());
for(int j = 0 ; j < tim[k][i].size() ; ++j) {
pos[k][i].pb(++Ncnt);
if(k == 1) dead[Ncnt] = i;
if(k == 0 && j != 0) add(pos[k][i][j],pos[k][i][j - 1]);
if(k == 1 && j != 0) add(pos[k][i][j - 1],pos[k][i][j]);
}
}
live[pos[0][i].back()] = i;
}
for(int i = 1 ; i <= M ; ++i) {
if(pre[i].ty == 0) {
add(getid(1,pre[i].x,pre[i].t),getid(1,pre[i].y,pre[i].t + 1));
add(getid(0,pre[i].y,pre[i].t + 1),getid(0,pre[i].x,pre[i].t));
}
else {
add(getid(0,pre[i].x,pre[i].t),getid(1,pre[i].y,pre[i].t));
add(getid(0,pre[i].y,pre[i].t),getid(1,pre[i].x,pre[i].t));
}
}
}
void Solve() {
queue<int> Q;
for(int i = 1 ; i <= Ncnt ; ++i) {
if(!deg[i]) Q.push(i);
}
while(!Q.empty()) {
int u = Q.front();Q.pop();que.pb(u);
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(!--deg[v]) Q.push(v);
}
}
for(int i = 0 ; i <= 100000 ; ++i) used.pb(i);
all.reset();
for(int j = que.size() - 1 ; j >= 0 ; --j) {
int u = que[j];pu[u] = used.back();used.pop_back();
reach[pu[u]].reset();
if(dead[u]) reach[pu[u]][dead[u]] = 1;
//cerr << "???" << endl;
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
reach[pu[u]] |= reach[pu[v]];
if(!--rec[v]) {
used.pb(pu[v]);
}
}
//cerr << "????" << endl;
if(live[u]) {
if(!reach[pu[u]][live[u]]) res[live[u]] = reach[pu[u]];
else all[live[u]] = 1;
}
if(!rec[u]) used.pb(pu[u]);
//cerr << "?????" << endl;
}
for(int i = 1 ; i <= N ; ++i) {
if(!all[i]) {
ans[i] = N - 1 - (res[i] | all).count();
}
out(ans[i]);space;
}
enter;
}
int main(){
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
}
