AT_arc234_b.Three Vertices
省选/NOI-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a connected simple undirected graph with N vertices and M edges. The vertices are numbered from 1 to N, and the i-th edge connects vertices ui and vi.
Each vertex is painted white or black. The initial state is represented by a string S of length N: vertex i is white if Si is 0, and black if it is 1.
A coloring is good if all vertices can be made white by performing the following operation any number of times, possibly zero.
- Choose three distinct vertices a,b,c such that a and b are connected by an edge and b and c are connected by an edge, and flip the color of each of these three vertices. That is, a white vertex becomes black, and a black vertex becomes white.
Here, vertices a and c may also be connected by an edge.
Process Q queries in the given order. The i-th query is as follows.
- Given an integer xi, flip the color of vertex xi. Then, determine whether the resulting coloring is good.
The color change in each query carries over to subsequent queries.
给你一个包含 N 个顶点和 M 条边的连通简单无向图。顶点编号为 1 到 N,第 i 条边连接顶点 ui 和 vi。
每个顶点被涂成白色或黑色。初始状态由一个长度为 N 的字符串 S 表示:若 Si 为 0,则顶点 i 为白色;若为 1,则为黑色。
一种染色方案被称为好的,当且仅当可以通过执行以下操作任意多次(包括零次),使得所有顶点均变为白色:
- 选择三个互不相同的顶点 a,b,c,满足 a 与 b 之间有边相连,且 b 与 c 之间也有边相连,并将这三个顶点的颜色全部翻转(即白色变黑色,黑色变白色)。
注意:顶点 a 与 c 之间也可能存在边。
按顺序处理 Q 个查询。第 i 个查询如下:
- 给定一个整数 xi,翻转顶点 xi 的颜色;然后判断当前染色方案是否为好的。
每次查询中的颜色翻转会持续影响后续查询。
输入格式
The input is given from Standard Input in the following format:
N M Q
S
u1 v1
u2 v2
⋮
uM vM
x1
x2
⋮
xQ
输入从标准输入中按以下格式给出:
N M Q
S
u1 v1
u2 v2
⋮
uM vM
x1
x2
⋮
xQ
输出格式
Output Q lines. On the i-th line, print Yes if the coloring after processing the i-th query is good, and No otherwise.
输出 Q 行。在第 i 行中,如果处理完第 i 个查询后的染色是合法的,则输出 Yes,否则输出 No。
输入输出样例
输入#1
3 3 5 100 1 2 2 3 3 1 1 1 2 3 2
输出#1
Yes No No Yes No
输入#2
4 3 4 1000 1 2 2 3 3 4 4 2 3 4
输出#2
Yes No No Yes
说明/提示
Sample 1 Explanation:
The colorings immediately after each query are 000, 100, 110, 111, and 101, in that order. Every operation on this graph flips all three vertices, so the coloring is good exactly when all three vertices have the same color. The answers to the first and fourth queries are therefore Yes.
Sample 2 Explanation:
Flipping the color of vertex 4 in the first query gives 1001. Performing the operations with (a,b,c)=(1,2,3),(2,3,4) in this order gives 0111 and then 0000, so the answer is Yes.
The second query starts from 1001 and flips the color of vertex 2, giving 1101.
Constraints
- 3≤N≤2×105
- N−1≤M≤2×105
- 1≤Q≤2×105
- S is a string of length N consisting of
0and1. - 1≤ui,vi≤N
- 1≤xi≤N
- The given graph is a connected simple undirected graph.
- All input numbers are integers.
样例 1 解释:
每次查询后立即得到的染色结果依次为 000、100、110、111 和 101。该图上的每次操作都会翻转全部三个顶点的颜色,因此染色是“良好”的当且仅当三个顶点颜色完全相同。故第一和第四次查询的答案均为 Yes。
样例 2 解释:
第一次查询中,翻转顶点 4 的颜色,得到 1001;接着按顺序执行操作 (a,b,c)=(1,2,3) 和 (a,b,c)=(2,3,4),分别得到 0111 和 0000,因此答案为 Yes。
第二次查询起始状态为 1001,翻转顶点 2 的颜色后得到 1101。
约束条件
- 3≤N≤2×105
- N−1≤M≤2×105
- 1≤Q≤2×105
- S 是一个长度为 N 的字符串,仅由字符
0和1组成。 - 1≤ui,vi≤N
- 1≤xi≤N
- 给定图是一个连通的简单无向图。
- 所有输入数据均为整数。
输入解题思路,AI测评打分。不知道怎么写?