QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100

# 4896. Alice、Bob 与 DFS

统计

Alice 和 Bob 又打算玩游戏了。

有一个点数为 $n$ 的有向无环图(点从 $1$ 开始编号),每个点要么是黑点,要么是白点。图中可能有重边,每个点的出边是有序的。

有一段 DFS 程序,其伪代码如下:

定义过程 dfs(u):
    if u 是白点
        按顺序遍历 u 的所有出边 (u,v)
            读取一个布尔值 g
            if g
                dfs(v)
    else
        按顺序遍历 u 的所有出边 (u,v) 
            dfs(v)

读取一个整数 r
dfs(r)

这段程序还有一个特殊性质:程序会在每次 dfs 过程调用开始前自动暂停

Alice 和 Bob 启动了 $k$ 个这样的程序,并给所有程序分别输入了一个点的编号作为 $r$(不同程序输入的 $r$ 可能不同)。现在,这些程序都在读取 $r$ 之后,调用 dfs(r) 之前暂停。

然后游戏开始。由 Alice 先手,双方轮流进行以下操作:

  • 选择一个尚未结束执行的程序,将其从暂停中恢复。继续执行该程序,直到它再次暂停或结束。在这个过程中,该程序每次读取 $g$,当前玩家都可以选择读取结果是 true 还是 false

每个程序都会在有限次暂停后结束,最终所有程序均会结束执行。如果轮到一名玩家操作时所有程序均已结束执行,该玩家输掉游戏,另一名玩家获胜。

双方都会采取最优策略。谁能获胜?

输入格式

第一行,一个正整数 $n$,表示图的点数。

第二行,$n$ 个整数 $c_1,c_2,\dots,c_n$,表示每个点的颜色。$c_u=0$ 表示 $u$ 是黑点,$c_u=1$ 表示 $u$ 是白点。

接下来 $n$ 行描述图中的边,其中第 $i$ 行有一个非负整数 $m_i$ 和 $m_i$ 个正整数 $e_{i,1},e_{i,2},\dots,e_{i,m_i}$,分别表示 $i$ 的出边数量和各出边的终点。为了方便,保证对于所有 $1\le i\le n$,$1\le j\le m_i$,有 $e_{i,j} \gt i$;即 $1,2,\dots,n$ 是该图的一个拓扑序。

接下来一行,一个正整数 $k$,表示程序数量。

最后一行,$k$ 个正整数 $r_1,r_2,\dots,r_k$,分别表示游戏开始前各程序的输入。

输出格式

一行,一个字符串,表示获胜者。如果 Alice 获胜,输出 Alice;如果 Bob 获胜,输出 Bob

样例一

input

4
1 0 1 0
1 2
2 4 3
1 4
0
1
2

output

Alice

explanation

该图有 $4$ 个点。

  • 点 $1$:白色,一条出边,终点为 $2$;
  • 点 $2$:黑色,两条出边,终点分别为 $4$、$3$;
  • 点 $3$:白色,一条出边,终点为 $4$;
  • 点 $4$:黑色,没有出边。

只有一个程序,其初始点为点 $2$。以下为双方采取最优策略时该程序的执行过程:

  1. 输入初始点 $r=2$ 并暂停执行。游戏开始,接下来轮到 Alice。因为只有一个程序,双方总是只能选择这个程序。Alice 选择继续执行该程序。
  2. $\texttt{dfs(2)}$
    1. 暂停执行。轮到 Bob。Bob 选择继续执行该程序。
    2. $\texttt{dfs(4)}$
      1. 过程返回
    3. 暂停执行。轮到 Alice。Alice 选择继续执行该程序。
    4. $\texttt{dfs(3)}$
      1. 读取一个布尔值 g。Alice 选择 false
      2. 过程返回
    5. 过程返回
  3. 结束执行。轮到 Bob。

轮到 Bob 时所有程序均已结束执行,Bob 输掉游戏,Alice 获胜。

在该样例中,点 $1$ 存在与否实际上对游戏过程没有影响。

另外,如果 Alice 在 $\texttt{dfs(3)}$ 中选择 true,那么接下来 $\texttt{dfs(3)}$ 会调用 $\texttt{dfs(4)}$,并在调用前多暂停一次。这会导致结束执行时轮到 Alice,获胜者会变成 Bob。由于双方均采取最优策略,这样的事情不会发生。

样例二

input

5
1 1 0 0 1
2 3 5
2 3 5
2 5 4
0
0
2
1 2

output

Bob

explanation

两个程序的初始点分别为 $1$ 和 $2$,而点 $1$ 和 $2$ 的颜色、出边完全一致,只有编号不同。

Bob 可以采取以下策略:当 Alice 选择执行某个程序后,Bob 选择执行另一个程序并给出相同的输入。容易证明这是 Bob 的必胜策略。

样例三

input

10
0 0 0 0 1 1 1 1 0 1
1 2
2 3 4
0
3 5 8 10
1 6
1 7
0
1 9
0
0
1
1

output

Bob

数据范围

对于所有数据:

  • $1\le n \le 2\times 10^5$
  • $c_i\in \{0,1\}$(对于所有 $1\le i\le n$)
  • $0\le m_i\le 4\times 10^5$(对于所有 $1\le i\le n$)
  • $\sum_{i=1}^n m_i \le 4\times 10^5$
  • $i \lt e_{i,j} \le n$(对于所有 $1\le i\le n$,$1\le j \le m_i$)
  • $1\le k \le 2\times 10^5$
  • $1\le r_i\le n$(对于所有 $1\le i\le k$)
子任务 分值 特殊限制
$1$ $5$ $c_i=0$(对于所有 $1\le i \le n$)
$2$ $15$ $k=1$,$r_1=1$
$3$ $15$ $n\le 10$,$\sum_{i=1}^n m_i \le 10$,$k\le 10$
$4$ $20$ $c_i=1$(对于所有 $1\le i \le n$);对于每个点 $u$,只有至多一条边的终点为 $u$;对于所有 $1\le i \le k$,图中不存在终点为 $r_i$ 的边
$5$ $20$ $c_i=1$(对于所有 $1\le i \le n$)
$6$ $25$ 没有额外的约束条件

时间限制:$2\texttt{s}$

空间限制:$256\texttt{MB}$