103054: [Atcoder]ABC305 E - Art Gallery on Graph

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:8 Solved:0

Description

Score : $475$ points

Problem Statement

There is a simple undirected graph with $N$ vertices and $M$ edges, where vertices are numbered from $1$ to $N$, and edges are numbered from $1$ to $M$. Edge $i$ connects vertex $a_i$ and vertex $b_i$.
$K$ security guards numbered from $1$ to $K$ are on some vertices. Guard $i$ is on vertex $p_i$ and has a stamina of $h_i$. All $p_i$ are distinct.

A vertex $v$ is said to be guarded when the following condition is satisfied:

  • there is at least one guard $i$ such that the distance between vertex $v$ and vertex $p_i$ is at most $h_i$.

Here, the distance between vertex $u$ and vertex $v$ is the minimum number of edges in the path connecting vertices $u$ and $v$.

List all guarded vertices in ascending order.

Constraints

  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq M \leq \min \left(\frac{N(N-1)}{2}, 2 \times 10^5 \right)$
  • $1 \leq K \leq N$
  • $1 \leq a_i, b_i \leq N$
  • The given graph is simple.
  • $1 \leq p_i \leq N$
  • All $p_i$ are distinct.
  • $1 \leq h_i \leq N$
  • All input values are integers.

Input

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

$N$ $M$ $K$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_M$ $b_M$
$p_1$ $h_1$
$p_2$ $h_2$
$\vdots$
$p_K$ $h_K$

Output

Print the answer in the following format. Here,

  • $G$ is the number of guarded vertices,
  • and $v_1, v_2, \dots, v_G$ are the vertex numbers of the guarded vertices in ascending order.
$G$
$v_1$ $v_2$ $\dots$ $v_G$

Sample Input 1

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

Sample Output 1

4
1 2 3 5

The guarded vertices are $1, 2, 3, 5$.
These vertices are guarded because of the following reasons.

  • The distance between vertex $1$ and vertex $p_1 = 1$ is $0$, which is not greater than $h_1 = 1$. Thus, vertex $1$ is guarded.
  • The distance between vertex $2$ and vertex $p_1 = 1$ is $1$, which is not greater than $h_1 = 1$. Thus, vertex $2$ is guarded.
  • The distance between vertex $3$ and vertex $p_2 = 5$ is $1$, which is not greater than $h_2 = 2$. Thus, vertex $3$ is guarded.
  • The distance between vertex $5$ and vertex $p_1 = 1$ is $1$, which is not greater than $h_1 = 1$. Thus, vertex $5$ is guarded.

Sample Input 2

3 0 1
2 3

Sample Output 2

1
2

The given graph may have no edges.


Sample Input 3

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

Sample Output 3

7
1 2 3 5 6 8 9

Input

题意翻译

### 题面 给定一张 $N$ 个点(编号为 $1 \sim N$),$M$ 条边的无向图,保证无重边无自环。现在有 $K$ 个被标记的点,其中第 $i$ 个被标记的点的编号为 $p_i$,任何从 $p_i$ 出发经过不超过 $h_i$ 条边能到达的点都会被染色(包括 $p_i$ 自身)。你需要求出这张图最终有哪些点被染色。 ### 输入格式 第一行三个正整数 $N,M,K$,含义见题目描述。 接下来 $M$ 行,每行两个正整数 $a_i,b_i$,表示编号为 $a_i,b_i$ 的点连有一条无向边。 接下来 $K$ 行,每行两个正整数 $p_i,h_i$,含义见题目描述。 ### 数据范围 $1 \le N \le 2 \times 10^5$,$0 \le M \le 2 \times 10^5$,$1 \le K,a_i,b_i,p_i,h_i \le N$,$p_i$ 互不相同。 保证给定的图无重边,无自环。

Output

得分:475分

问题描述

有一个简单的无向图,包含N个顶点和M条边,顶点编号为1到N,边编号为1到M。第i条边连接顶点$a_i$和顶点$b_i$。
有K个编号为1到K的安全警卫位于一些顶点上。警卫i位于顶点$p_i$,具有耐力$h_i$。所有$p_i$都是不同的。

当满足以下条件时,顶点v被认为是“被保护的”:

  • 至少存在一个警卫i,使得顶点v和顶点$p_i$之间的距离不超过$h_i$。

这里,顶点u和顶点v之间的距离是连接顶点u和顶点v的路径中边的数量的最小值。

按升序列出所有被保护的顶点。

约束条件

  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq M \leq \min \left(\frac{N(N-1)}{2}, 2 \times 10^5 \right)$
  • $1 \leq K \leq N$
  • $1 \leq a_i, b_i \leq N$
  • 给定的图是简单的。
  • $1 \leq p_i \leq N$
  • 所有$p_i$都是不同的。
  • $1 \leq h_i \leq N$
  • 所有输入值都是整数。

输入

输入通过标准输入以以下格式给出:

$N$ $M$ $K$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_M$ $b_M$
$p_1$ $h_1$
$p_2$ $h_2$
$\vdots$
$p_K$ $h_K$

输出

以以下格式打印答案。这里,

  • $G$是被保护的顶点的数量,
  • 顶点$v_1, v_2, \dots, v_G$是按升序排列的被保护的顶点的编号。
$G$
$v_1$ $v_2$ $\dots$ $v_G$

样例输入1

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

样例输出1

4
1 2 3 5

被保护的顶点是1, 2, 3, 5。
这些顶点是由于以下原因被保护的。

  • 顶点1和顶点$p_1 = 1$之间的距离为0,不超过$h_1 = 1$。因此,顶点1被保护。
  • 顶点2和顶点$p_1 = 1$之间的距离为1,不超过$h_1 = 1$。因此,顶点2被保护。
  • 顶点3和顶点$p_2 = 5$之间的距离为1,不超过$h_2 = 2$。因此,顶点3被保护。
  • 顶点5和顶点$p_1 = 1$之间的距离为1,不超过$h_1 = 1$。因此,顶点5被保护。

样例输入2

3 0 1
2 3

样例输出2

1
2

给定的图可能没有边。


样例输入3

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

样例输出3

7
1 2 3 5 6 8 9

加入题单

上一题 下一题 算法标签: