#3118. 「IOI2017」玩具火车

内存限制:256 MiB 时间限制:2000 ms 题目类型:交互
上传者: 匿名

题目描述

Arezou 和她的兄弟 Borzou 是双胞胎。他们收到的生日礼物是一套好玩的玩具火车。他们用它建了一个由 n 个车站和 m 段单向轨道的铁路系统。这些车站的编号是从 0 n - 1 。每段轨道都始于某一车站,然后终于同一车站或其他车站。每个车站至少会有一段轨道以它为起点。

其中有些车站是充电车站。无论何时,如果火车抵达某个充电车站。无论何时,如果火车抵达某个充电车站,它都会被充到满电。满电火车拥有足够的动力连续地驶过 n 段轨道,但是如果不再充电的话,在即将进入第 n + 1 段轨道时它就会因电已用光而停车。

每个车站都有一个轨道开关,可以扳向任一以该车站为起点的轨道。火车从某个车站驶出时,驶向的正是该车站的开关所扳向的轨道。

这对双胞胎打算用他们的火车玩个游戏。他们已经分完了所有的车站:每个车站要么归 Arezou,要么归 Borzou。游戏里面只有一列火车。游戏开始时,这列火车停在车站 s ,并且充满了电。为启动游戏,车站 s 的拥有者把车站 s 的开关扳向某个以 s 为起点的轨道。随后他们启动火车,火车也就开始沿着轨道行驶。

无论何时,在火车首次进入某一车站时,该车站的拥有者都要扳定车站开关。开关一旦扳定,它就会保持状态不变直到游戏结束。因此,火车如果开到了一个曾经进过的车站,就会沿着与之前相同的轨道开出该车站。

由于车站数量是有限的,火车的行驶最终都会落入某个环路。环路是指一系列不同的车站 c_0, c_1, \cdots , c_{k - 1} ,其中火车在离开车站 c_i(0 \leq i < k - 1) 后驶上连向车站 c_{i + 1} 的轨道,在离开车站 c_{k - 1} 后驶上连向车站 c_0 的轨道。一个环路可能只包括一个车站(此时 k = 1 ),即火车从车站 c_0 驶出后又驶上了连向车站 c_0 的轨道。

如果火车能够连续行驶跑完,Arezou 就赢了。否则火车最后会把电用光而停车,这样 Borzou 就赢了。换句话说,如果在车站 c_0, c_1, \cdots , c_{k - 1} 中至少有一个充电车站,且使得火车能够不断地充电而沿着环路跑个没完,Arezou 赢。否则,它就会最终把电用光(有可能是在沿着环路跑好几圈后),Borzou 赢。

现在给你一个这样的铁路系统。Arezou 和 Borzou 将会玩 n 轮游戏。其中在第 s 轮游戏中 (0 \leq s \leq n - 1) ,火车最初停在车站 s 上。你的任务是,对每一轮游戏,判断是否无论 Borzou 怎么玩,Arezou 都必胜。

输入格式

你需要实现下面的函数:

int[] who_wins(int[] a, int[] r, int[] u, int[] v)
  • a :长度为 n 的数组。如果 Arezou 拥有车站 i ,则 a_i = 1 ;否则 Borzou 拥有车站 i ,且 a_i=0
  • r :长度为 n 的数组。如果车站 i 是充电车站,则 r_i = 1 ;否则 r_i=0
  • u v :长度为 m 的数组。对于所有 0 \leq i \leq m - 1 ,存在某一单向轨道,其起点为 u_i ,终点为 v_i
  • 该函数需要返回一个长度为 n 的数组 w 。对于每个 0 \leq i \leq n - 1 ,如果在火车最初停在车站 i 的游戏中,不管 Borzou 怎么玩,Arezou 都能赢,则 w_i 的值应为 1 。否则 w_i 的值应为 0

样例

who_wins([0, 1], [1, 0], [0, 0, 1, 1], [0, 1, 0, 1])

QQ截图20190509135110.png

  • 这里有 2 个车站。Borzou 拥有充电车站 0 。Arezou拥有车站 1 ,但是它不是充电车站。
  • 这里有 4 段轨道 (0,0),(0,1),(1,0) (1,1) ,其中 (i,j) 表示一个以车站 i 为起点、车站 j 为终点的单向轨道。
  • 考虑火车最初停在车站 0 的游戏。如果 Borzou 将车站 0 的开关扳向轨道 (0,0) ,那么火车就会沿着这个环形轨道绕个没完(注意,车站 0 是一个充电车站)。在这种情况下,Arezou 赢。否则,如果 Borzou 把车站 0 的开关扳向轨道 (0,1) ,Arezou 可以把车站 1 的开关扳向轨道 (1,0) 。这样的话,火车将会在两个车站之间绕个不停。Arezou 还是会赢,因为车站 0 是充电车站,火车将跑个没完。因此,无论 Borzou 怎么玩,Arezou 都会赢。
  • 根据类似的逻辑,在火车最初停在车站 1 的游戏中,无论 Borzou 怎么玩,Arezou 也都会赢。因此,函数应当返回 [1, 1]

在压缩附件包里的文件 examples/01.inexamples/01.out 对应于上述例子。

数据范围与提示

限制条件:

  • 1 \leq n \leq 5, 000
  • n \leq m \leq 20, 000
  • 至少会有一个充电车站。
  • 每个车站至少会有一段轨道以它为起点。
  • 可能有某个轨道的起点和终点是相同的(即 u_i = v_i )。
  • 所有轨道两两不同。也就是说,也就是说,不存在这样的两个下标 i, j(0 \leq i < j \leq m - 1) ,使得 u_i = u_j v_i = v_j
  • 对于所有 0 \leq i \leq m - 1 ,都有 0 \leq u_i, v_i \leq n - 1

子任务:

  1. (5分)对于所有有向轨道,都有 v = u 或者 v = u + 1
  2. (10分) n \leq 15
  3. (11分)Arezou 拥有所有车站。
  4. (11分)Borzou 拥有所有车站。
  5. (12分)充电车站的数量为 1。
  6. (51分)没有任何的附加限制。

评分程序样例:

评分程序样例将会读入以下格式的数据:

  • 1 行: n\ m
  • 2 行: a_0\ a_1\ \cdots\ a_{n - 1}
  • 3 行: r_0\ r_1\ \cdots\ r_{n - 1}
  • 4 + i 行(对于所有 0 \leq i \leq m - 1 ): u_i\ v_i

评分程序样例将会按照下述格式打印出 who_wins 的返回结果:

  • 1 行: w_0\ w_1\ \cdots\ w_{n - 1}