分析
每个人在每个时刻只有 $2$ 种状况，考虑 2-SAT 。
设 $(x,t,0/1)$ 表示 $x$ 在 $t$ 时刻活着/死了。那么直接连边就好了。
另外还有一个隐藏条件：如果 $x$ 在 $t$ 时刻活着，那么在 $t-1$ 时刻也活着；如果 $x$ 在 $t$ 时刻死了，那么 $x$ 在 $t+1$ 时刻也死了。这个同样要连边。
问题变为在建好的图上，从 $(i,T+1,0)$ 出发，可以到达多少个 $(j,T+1,1)$ 。假设有 $ans$ 个，那么答案为 $n-ans-1$ 。
这个东西怎么求呢？可以用 $\mathrm{bitset}$ 维护一下，然后拓扑排序转移。时间复杂度为 $O(\frac{Tnm}{\omega})$ 。
这样子显然过不去，原因是点数太多了。考虑怎么优化点数。
显然只有至多 $4m$ 个点是有用的（每个预言只和 $4$ 个点有关）。那么把这 $4m$ 个点拿出来建图就行了。
注意上面的隐藏条件也要建：对于 $x$ 相同的点，按 $t$ 排序，然后依次连边。
这样子 $\mathrm{bitset}$ 还是存不下，可以分段跑。
另外还有一些要注意的地方：
- 如果从 $(i,T+1,0)$ 可以到达 $(i,T+1,1)$ ，那么说明 $i$ 必死。显然此时 $i$ 的答案为 $0$ 。另外这样的 $i$ 也不会对别的点产生贡献，注意判掉。
- 对于某些人，可能没有与他有关的预言，那么他最后一定可以活着。注意处理这一部分。
具体实现和细节见代码。
代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=400000+10;
const int B=10000;
struct Edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
static int cnt=0;
e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}
int n,m,T,tot;
bitset<B> bit[N],tmp;
map<pair<int,int>,int> mp;
vector<pair<int,int>> same[N];
queue<int> Q;
int lst[N],now[N],deg[N],tag[N],ans[N];
inline int id(int x,int y) { return (x<<1)+y-1; }
inline int calcid(int x,int y) {
map<pair<int,int>,int>::iterator it=mp.find(make_pair(x,y));
if (it==mp.end()) {
int res=++tot;
mp[make_pair(x,y)]=res;
same[x].push_back(make_pair(y,res));
return res;
}
else return it->second;
}
int main() {
T=read(),n=read(),m=read();
for (re int i=1;i<=m;++i) {
int op=read(),t=read(),x=read(),y=read();
if (!op) {
x=calcid(x,t),y=calcid(y,t+1);
addEdge(id(x,0),id(y,0)),++deg[id(y,0)];
addEdge(id(y,1),id(x,1)),++deg[id(x,1)];
} else {
x=calcid(x,t),y=calcid(y,t);
addEdge(id(x,1),id(y,0)),++deg[id(y,0)];
addEdge(id(y,1),id(x,0)),++deg[id(x,0)];
}
}
for (re int i=1;i<=n;++i) {
sort(same[i].begin(),same[i].end());
for (re int j=1;j<same[i].size();++j) {
int u=same[i][j-1].second,v=same[i][j].second;
addEdge(id(u,0),id(v,0)),++deg[id(v,0)];
addEdge(id(v,1),id(u,1)),++deg[id(u,1)];
}
if (same[i].size()) lst[i]=(--same[i].end())->second;
else lst[i]=-1;
}
for (re int l=1,r=min(B,n);l<=n;l=r+1,r=min(l+B-1,n)) {
for (re int i=1;i<=(tot<<1);++i) bit[i].reset();
for (re int i=l;i<=r;++i)
if (~lst[i]) bit[id(lst[i],1)].set(i-l);
for (re int i=1;i<=(tot<<1);++i) {
now[i]=deg[i];
if (!now[i]) Q.push(i);
}
while (!Q.empty()) {
int u=Q.front(); Q.pop();
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v; bit[v]|=bit[u],--now[v];
if (!now[v]) Q.push(v);
}
}
tmp.reset();
for (re int i=l;i<=r;++i)
if (~lst[i]&&bit[id(lst[i],0)][i-l])
tag[i]=1,tmp.set(i-l);
for (re int i=1;i<=n;++i) {
if (~lst[i]) ans[i]+=(bit[id(lst[i],0)]|tmp).count();
else ans[i]+=tmp.count();
}
}
for (re int i=1;i<=n;++i) printf("%d ",tag[i]?0:n-ans[i]-1);
puts("");
return 0;
}