#3101. 「JSOI2019」精准预测

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目背景

JYY 和他的火星探险队再次登录火星小镇,并且打算把机器学习的知识传授给火星人,从而提高火星人的生活效率。但智力有限的火星人纷纷表示不相信计算机科学。为了让火星人彻底信服,JYY 的探险队找到了他们之前关于火星详细的数据记录,并且训练了一个预测模型,这个模型能准确地预测出火星人在未来的生死情况。

题目描述

目前,火星小镇上有 n 个居民(编号 1, 2, \ldots, n )。机器学习算法预测出这些居民在接下来 T 个时刻(编号 1, 2, \ldots , T )的生死情况,每条预测都是如下两种形式之一:

  • 难兄难弟 0\ t\ x\ y :在 t 时刻,如果 x 是死亡状态,那么在 t + 1 时刻, y 是死亡状态。(注意,当 x t 时刻是生存状态时,该预测也被认为是正确的);
  • 死神来了 1\ t\ x\ y :在 t 时刻,如果 x 是生存状态,那么在 t 时刻, y 是死亡状态。(注意,当 x t 时刻是死亡状态时,该预测也被认为是正确的)。

注意本题是对某个时刻进行生死状态的预测,如果某个人在 t 时刻是生存状态,在 t + 1 时刻是死亡状态,你可以认为是在 t t + 1 这段时间内发生了某个事件导致其死亡。

虽然 JYY 对自己从大数据中统计得到的模型非常自信,但火星人看到这些预测吓了一跳,表示实在难以接受这种设定,更是认为计算机科学是可怕的邪教,打破了他们平静的生活。为了安抚火星人的情绪, JYY 打算从这些预测结果中推导出一些火星人更容易接受的事实,从而安抚火星人的情绪。

具体来说,JYY 首先假设对火星人生死的预测全部正确,在此基础上,JYY 希望为小镇上的每个居民 k 分别计算有多少个火星人有可能和他一起活到第 T+1 时刻,换言之,JYY 希望为每个火星人 k 计算

\sum_{1\le i\le n,i\neq k} \text{Live}(k,i)

其中 \text{Live}(i, j) = 1 表示编号为 i j 的火星人有可能同时在第 T + 1 时刻处于生还状态,否则 \text{Live}(i, j) = 0

注意火星人是不能够复活的。一个火星人可能在时刻 1 就处于死亡状态,也有可能有预测未覆盖的死亡情况发生(火星人在任何时候都可能死亡,但任意时刻观察到火星人的状态要么活着,要么死亡)。最后,注意到 \text{Live} 是为每一对火星人分别独立计算的,因此 \text{Live}(x, y) = \text{Live}(y, z) = 1 并不意味着 \text{Live}(x, z) = 1

输入格式

输入第一行包含三个整数 T, n, m
接下来有 m 行,每行表示一条预言,每条预言第一个整数 c 表示预言的类型:

  • c = 0 :接下来读入 t, x, y
  • c = 1 :接下来读入 t, x, y

输出格式

输出 n 个数表示答案,用空格分割。

样例

样例输入

3 3 2
0 2 1 3
1 1 2 3

样例输出

2 1 1

样例说明

如果编号为 2 的火星人活到 T + 1 时刻,意味着在 1 时刻他也是活着的,由于第二条预言,会观察到编号为 3 的火星人在时刻 1 是死亡状态,所以编号为 2 3 的火星人不能同时活到 T + 1 时刻,所以 \text{Live}(2, 3) = 0

而编号为 1 的火星人能和其他两人的某一个活到 T + 1 时刻。注意当 1 3 同时活着的时候,第一条预言是正确的。所以有 \text{Live}(1, 2) = 1, \text{Live}(1, 3) = 1

样例 2

见附加文件 predict2.in/ans

数据范围与提示

测试点 T n m
1 \le 2 \le 10 \le 10
2,3 \le 100 \le 100 \le 200
4 \le 10^6 \le 3\times 10^3 \le 6\times 10^3
5,6 \le 4\times 10^4 \le 10^4 \le 2\times 10^4
7 \le 10^6 \le 3\times 10^4 \le 6\times 10^4
8 \le 4\times 10^4 \le 8\times 10^4
9,10 \le 5\times 10^4 \le 10^5

输入数据保证 1 \le t \le T,1 \le x, y \le n

提示

本题内存限制 1024MiB 包含进程中运行库、堆栈等所有内存,请特别留意。