AT_abc216_d.[ABC216D] Pair of Balls

普及+/提高

通过率:0%

AC君温馨提醒

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

题目描述

有 2N2N 个球。每个球被涂上了一个用 11 到 NN 之间的整数表示的颜色,并且每种颜色恰好有 22 个球。

这些球被放入了 MM 根底部与地面平行的筒中。最开始,第 ii 根筒(1≤i≤M1 \leq i \leq M)中有 kik_i 个球,从上到下第 jj 个球的颜色为 ai,ja_{i,j}。

你的目标是通过重复以下操作,使所有 MM 根筒都变为空:

  • 选择两根不同且非空的筒,各自取出最上面的一个球并丢弃。此时,取出的两个球必须颜色相同。

请判断是否有可能达成目标。

输入格式

输入以以下格式从标准输入读入。

NN MM
k1k_1 a1,1a_{1,1} a1,2a_{1,2} …\ldots a1,k1a_{1,k_1}
k2k_2 a2,1a_{2,1} a2,2a_{2,2} …\ldots a2,k2a_{2,k_2}
⋮\vdots
kMk_M aM,1a_{M,1} aM,2a_{M,2} …\ldots aM,kMa_{M,k_M}

输出格式

如果目标可以达成,输出 Yes;否则输出 No。

输入输出样例

  • 输入#1

    2 2
    2
    1 2
    2
    1 2

    输出#1

    Yes
  • 输入#2

    2 2
    2
    1 2
    2
    2 1

    输出#2

    No

说明/提示

限制条件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 2≤M≤2×1052 \leq M \leq 2 \times 10^5
  • 1≤ki (1≤i≤M)1 \leq k_i\ (1 \leq i \leq M)
  • 1≤ai,j≤N (1≤i≤M,1≤j≤ki)1 \leq a_{i,j} \leq N\ (1 \leq i \leq M, 1 \leq j \leq k_i)
  • ∑i=1Mki=2N\sum_{i=1}^{M} k_i = 2N
  • 对于每个 x (1≤x≤N)x\ (1 \leq x \leq N),存在恰好两个整数对 (i,j)(i, j) 满足 1≤i≤M1 \leq i \leq M,1≤j≤ki1 \leq j \leq k_i 且 ai,j=xa_{i,j} = x
  • 输入均为整数

样例解释 1

可以按如下方式进行操作:

  1. 选择第 1 根筒和第 2 根筒,各自取出最上面的球并丢弃。两球颜色均为 11,操作有效。
  2. 选择第 1 根筒和第 2 根筒,各自取出最上面的球并丢弃。两球颜色均为 22,操作有效。

样例解释 2

由于无法进行任何一次操作,因此无法达成目标,即无法将所有 MM 根筒都变为空。

由 ChatGPT 4.1 翻译

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

首页