AT_arc234_b.Three Vertices

省选/NOI-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given a connected simple undirected graph with NN vertices and MM edges. The vertices are numbered from 11 to NN, and the ii-th edge connects vertices uiu_i and viv_i.

Each vertex is painted white or black. The initial state is represented by a string SS of length NN: vertex ii is white if SiS_i 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,ca,b,c such that aa and bb are connected by an edge and bb and cc 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 aa and cc may also be connected by an edge.

Process QQ queries in the given order. The ii-th query is as follows.

  • Given an integer xix_i, flip the color of vertex xix_i. Then, determine whether the resulting coloring is good.

The color change in each query carries over to subsequent queries.

给你一个包含 NN 个顶点和 MM 条边的连通简单无向图。顶点编号为 11 到 NN,第 ii 条边连接顶点 uiu_i 和 viv_i。

每个顶点被涂成白色或黑色。初始状态由一个长度为 NN 的字符串 SS 表示:若 SiS_i 为 0,则顶点 ii 为白色;若为 1,则为黑色。

一种染色方案被称为好的,当且仅当可以通过执行以下操作任意多次(包括零次),使得所有顶点均变为白色:

  • 选择三个互不相同的顶点 a,b,ca, b, c,满足 aa 与 bb 之间有边相连,且 bb 与 cc 之间也有边相连,并将这三个顶点的颜色全部翻转(即白色变黑色,黑色变白色)。

注意:顶点 aa 与 cc 之间也可能存在边。

按顺序处理 QQ 个查询。第 ii 个查询如下:

  • 给定一个整数 xix_i,翻转顶点 xix_i 的颜色;然后判断当前染色方案是否为好的。

每次查询中的颜色翻转会持续影响后续查询。

输入格式

The input is given from Standard Input in the following format:

NN MM QQ
SS
u1u_1 v1v_1
u2u_2 v2v_2
⋮\vdots
uMu_M vMv_M
x1x_1
x2x_2
⋮\vdots
xQx_Q

输入从标准输入中按以下格式给出:

NN MM QQ
SS
u1u_1 v1v_1
u2u_2 v2v_2
⋮\vdots
uMu_M vMv_M
x1x_1
x2x_2
⋮\vdots
xQx_Q

输出格式

Output QQ lines. On the ii-th line, print Yes if the coloring after processing the ii-th query is good, and No otherwise.

输出 QQ 行。在第 ii 行中,如果处理完第 ii 个查询后的染色是合法的,则输出 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 44 in the first query gives 1001. Performing the operations with (a,b,c)=(1,2,3),(2,3,4)(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 22, giving 1101.

Constraints

  • 3≤N≤2×1053 \le N \le 2 \times 10^5
  • N−1≤M≤2×105N-1 \le M \le 2 \times 10^5
  • 1≤Q≤2×1051 \le Q \le 2 \times 10^5
  • SS is a string of length NN consisting of 0 and 1.
  • 1≤ui,vi≤N1 \le u_i,v_i \le N
  • 1≤xi≤N1 \le x_i \le N
  • The given graph is a connected simple undirected graph.
  • All input numbers are integers.

样例 1 解释:
每次查询后立即得到的染色结果依次为 000、100、110、111 和 101。该图上的每次操作都会翻转全部三个顶点的颜色,因此染色是“良好”的当且仅当三个顶点颜色完全相同。故第一和第四次查询的答案均为 Yes。

样例 2 解释:
第一次查询中,翻转顶点 44 的颜色,得到 1001;接着按顺序执行操作 (a,b,c)=(1,2,3)(a,b,c)=(1,2,3) 和 (a,b,c)=(2,3,4)(a,b,c)=(2,3,4),分别得到 0111 和 0000,因此答案为 Yes。

第二次查询起始状态为 1001,翻转顶点 22 的颜色后得到 1101。

约束条件

  • 3≤N≤2×1053 \le N \le 2 \times 10^5
  • N−1≤M≤2×105N-1 \le M \le 2 \times 10^5
  • 1≤Q≤2×1051 \le Q \le 2 \times 10^5
  • SS 是一个长度为 NN 的字符串,仅由字符 0 和 1 组成。
  • 1≤ui,vi≤N1 \le u_i,v_i \le N
  • 1≤xi≤N1 \le x_i \le N
  • 给定图是一个连通的简单无向图。
  • 所有输入数据均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页