E - Art Gallery on Graph

Contest Duration: 2023-06-10(Sat) 12:00 - 2023-06-10(Sat) 13:40 (local time) (100 minutes) Back to Home

E - Art Gallery on Graph Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $475$ 点

問題文

頂点に $1$ から $N$ の、辺に $1$ から $M$ の番号がついた $N$ 頂点 $M$ 辺の単純無向グラフがあります。辺 $i$ は頂点 $a_i$ と頂点 $b_i$ を結んでいます。
$1$ から $K$ までの番号がついた $K$ 人の警備員が頂点上にいます。警備員 $i$ は頂点 $p_i$ にいて、体力は $h_i$ です。ここで全ての $p_i$ は互いに異なります。

頂点 $v$ が次の条件を満たす時、頂点 $v$ を 警備されている頂点 と呼びます。

頂点 $v$ と頂点 $p_i$ の距離が $h_i$ 以下であるような警備員 $i$ が少なくとも 1 人存在する。

ここで、頂点 $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$

入力例 1Copy

Copy

出力例 1Copy

Copy

4
1 2 3 5

警備されている頂点は $1, 2, 3, 5$ の $4$ 頂点です。
これらの頂点が警備されている頂点である理由は以下の通りです。

頂点 $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$ は警備されている頂点です。

入力例 2Copy

Copy

3 0 1
2 3

出力例 2Copy

Copy

1
2

入力で与えられるグラフに辺がない場合もあります。

入力例 3Copy

Copy

出力例 3Copy

Copy

7
1 2 3 5 6 8 9

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 1Copy

Copy

Sample Output 1Copy

Copy

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 2Copy

Copy

3 0 1
2 3

Sample Output 2Copy

Copy

1
2

The given graph may have no edges.

Sample Input 3Copy

Copy

Sample Output 3Copy

Copy

7
1 2 3 5 6 8 9