比赛场次 471
比赛名称 USACO银组复现(ION ONLINE模拟赛)
比赛状态 已结束比赛成绩
开始时间 2020-04-06 14:00:00
结束时间 2020-04-06 17:30:00
开放分组 全部用户
注释介绍 入门组模拟
题目名称 Cowntact Tracing
输入输出 usaco_20Open_tracing.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 16 简单对比
用户 结果 时间 内存 得分
Gravatar锝镆氪锂铽 AWWWAWWWWWWWWWWW 0.009 s 13.66 MiB 12

Cowntact Tracing

★☆   输入文件:usaco_20Open_tracing.in   输出文件:usaco_20Open_tracing.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

由于高传染性的牛传染病 COWVID-19 的爆发,Farmer John 非常担忧他的奶牛们(编号为 $1 \ldots N$)的健康。

最近,Farmer John 对他的所有奶牛进行了检测,发现有一部分奶牛对该疾病的检测结果呈阳性。利用牛棚内的视频监控,他得以查看最近的奶牛之间的互动行为,结果发现奶牛们互相打招呼时,她们会握蹄,不幸的是这是一种会将疾病从一头奶牛传播给另一头奶牛的行为。Farmer John 汇总了一个添加了时间戳的清单,每条数据的形式为 $(t, x, y)$,表示在时间 $t$,奶牛 $x$ 与奶牛 $y$ 握了蹄。Farmer John 同时还知道以下信息:

 • 1. 他的农场上恰有一头奶牛最初带有携带疾病(我们将这头奶牛称为“零号病人”)。

 • 2. 一旦一头奶牛被感染,她会在接下来的 $K$ 次握蹄中传染疾病(可能会与同一头奶牛握蹄多次)。握蹄 $K$ 次后,她不再在此后的握蹄中传染疾病(因为此时她意识到了她会传染疾病,于是会仔细地洗蹄)。

 • 3. 一旦一头奶牛被感染,她会持续处于被感染状态。

不幸的是,Farmer John 不知道他的 $N$ 头奶牛中的哪一头是零号病人,也不知道 $K$ 的值!基于他的数据,请帮助他缩小这些未知量的范围。保证至少有一种可能的情况。

【输入格式】

输入的第一行包含 $N$($2 \leq N \leq 100$)和 $T$($1 \leq T \leq 250$)。 

下一行包含一个长为 $N$ 的字符串,每个字符均为 0 或 1,表述目前 Farmer John 的 $N$ 头奶牛的状态——0 表示一头健康的奶牛,1 表示一头染病的奶牛。

以下 $T$ 行每行包含 Farmer John 的互动清单中的一条记录,由三个整数 $t$、$x$ 和 $y$组成,其中 $t$ 为一次互动发生的正整数时间($t \leq 250$),$x$ 和 $y$ 为范围 $1 \ldots N$ 内的不同整数,表示时间 $t$ 握蹄的两头奶牛。在每一时刻至多只有一次互动发生。

【输出格式】

输出一行,包含三个整数 $x$、$y$ 和 $z$,其中 $x$ 为可能为零号病人的奶牛数量,$y$ 为与数据一致的最小可能 $K$ 值,$z$ 为与数据一致的最大可能 $K$ 值(如果通过数据无法推断 $K$ 的上界,$z$ 输出 "Infinity")。

注意:可能有 $K=0$。

【样例输入】

4 3
1100
7 1 2
5 2 3
6 2 4

【样例输出】

1 1 Infinity

【样例解释】

唯一可能是零号病人的是奶牛 1。

对于所有的 $K>0$,奶牛 1 在时刻 7 感染奶牛 2,而奶牛 3 和奶牛 4 均不会被感染。

【提示】

对于 $100\%$ 的测试数据,均满足上文所给出的数据规模。

【来源】

USACO 美国公开赛 Bronze 组