比赛场次 511
比赛名称 近5年noip/csp题目回顾
比赛状态 已结束比赛成绩
开始时间 2022-06-25 08:30:00
结束时间 2022-06-26 17:30:00
开放分组 全部用户
注释介绍 只有历年比赛题才最接近比赛题。
题目名称 魔法值
输入输出 2020_magic.in/out
时间限制 1000 ms (1 s)
内存限制 512 MiB
测试点数 20 简单对比
用户 结果 时间 内存 得分

魔法值

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

【题目描述】

$H$ 国的交通由 $n$ 座城市与 $m$ 条道路构成,城市与道路都从 $1$ 开始编号,其中 $1$ 号城市是 $H$国的首都。$H$ 国中一条道路将把两个不同城市直接相连,且任意两个城市间至多有一条道路。

$H$ 国是一个信奉魔法的国家,在第 $j$ 天,$i$ 号城市的魔法值为 $f_{i,j}$。$H$ 国的魔法师已观测到第 $0$ 天时所有城市的魔法值 $f_{i,0}$,且他们还发现,之后的每一天每个城市的魔法值,都将会变为所有与该城市直接相连的城市的前一天魔法值的异或值,即

$f_{x,j}$ $=$ $f_{v_1,j-1}$ $xor$ $f_{v_2,j-1}$ $xor$ $\ldots$ $xor$ $f_{v_k,j-1}$

其中$j \geq 1$且$v_1....v_k$是与$x$直接相连的城市

现在 $H$ 国的国王问了你$q$个问题,对于第$i$个问题你需要回答:第$a_i$天时首都的魔法值是多少。

【输入格式】

第一行三个用空格分隔的整数$n,m,q$表示城市数、道路数与问题数。

第二行$n$个用空格分隔的整数,第$i$个整数表示$f_{i,0}$。

接下来$m$行,每行两个用空格分隔的正整数 $u,v$表示一条连接$u$号城市与$v$号城市的道路。

接下来$q$行每行一个整数,第$i$行的整数表示$a_i$。

【输出格式】

按顺序输出$q$行每行一个整数,表示对应问题的答案

【样例输入】

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

【样例输出】

1

【提示】

对于 $20$% 的数据,满足:$a_i \leq 100$

对于 $40$% 的数据,满足:$1 \leq n \leq 20$

另有 $30$% 的数据,满足:$m = \frac{n(n-1)}{2}$

对于 $100$% 的数据,满足:$1 \leq n , q \leq 100 \ , \ 1 \leq m \leq \frac{n(n-1)}{2}, 1 \leq a_i < 2^{32} \ , \ 0 \leq f_{i,0} < 2^{32}$

【来源】

$NOI$ $Online$能力测试 第$3$场 提高组 $problem$ $2$