E - Nearest Black Vertex

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

E - Nearest Black Vertex Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

$N$ 個の頂点と $M$ 本の辺からなる、単純（自己ループおよび多重辺を含まない）かつ連結な無向グラフが与えられます。
$i = 1, 2, \ldots, M$ について、 $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結ぶ無向辺です。

各頂点を白または黒で塗る方法であって、下記の $2$ つの条件をともに満たすものが存在するかを判定し、存在する場合はその一例を示してください。

$1$ 個以上の頂点が黒で塗られている。
すべての $i = 1, 2, \ldots, K$ について、下記の条件が成り立つ。
- 頂点 $p_i$ と「黒で塗られた頂点のうち頂点 $p_i$ からの距離が最小であるもの」の距離がちょうど $d_i$ である。

ここで、頂点 $u$ と頂点 $v$ の距離は、 $u$ と $v$ を結ぶパスの辺の本数としてあり得る最小値として定義されます。

制約

$1 \leq N \leq 2000$
$N-1 \leq M \leq \min\lbrace N(N-1)/2, 2000 \rbrace$
$1 \leq u_i, v_i \leq N$
$0 \leq K \leq N$
$1 \leq p_1 \lt p_2 \lt \cdots \lt p_K \leq N$
$0 \leq d_i \leq N$
与えられるグラフは単純かつ連結
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $M$ 
 $u_1$   $v_1$ 
 $u_2$   $v_2$ 
 $\vdots$ 
 $u_M$   $v_M$ 
 $K$ 
 $p_1$   $d_1$ 
 $p_2$   $d_2$ 
 $\vdots$ 
 $p_K$   $d_K$

出力

問題文中の条件を満たすように各頂点を白または黒で塗る方法が存在しない場合は、No を出力せよ。
存在する場合は、下記の形式の通り、 $1$ 行目に Yes と出力し、 $2$ 行目に各頂点を塗る方法を表す文字列 $S$ を出力せよ。ここで、 $S$ は長さ $N$ の文字列であり、 $i = 1, 2, \ldots, N$ について $S$ の $i$ 文字目は、頂点 $i$ を黒で塗るとき $1$ 、白で塗るとき $0$ である。

Yes
 $S$

答えが複数ある場合、どれを出力しても正解とみなされる。

入力例 1Copy

Copy

出力例 1Copy

Copy

Yes
10100

例えば、頂点 $1, 3$ を黒に、頂点 $2, 4, 5$ を白に塗るという方法が、問題文中の条件を満たします。
実際、 $i = 1, 2, 3, 4, 5$ について、頂点 $i$ と「黒で塗られた頂点のうち頂点 $i$ からの距離が最小であるもの」の距離を $A_i$ で表すと、 $(A_1, A_2, A_3, A_4, A_5) = (0, 1, 0, 1, 2)$ であり、特に、 $A_1 = 0, A_5 = 2$ が成り立ちます。

入力例 2Copy

Copy

出力例 2Copy

Copy

No

問題文中の条件を満たすように各頂点を白または黒で塗る方法が存在しないため、No を出力します。

入力例 3Copy

Copy

1 0
0

出力例 3Copy

Copy

Yes
1

Score : $500$ points

Problem Statement

You are given a simple connected undirected graph with $N$ vertices and $M$ edges (a simple graph contains no self-loop and no multi-edges).
For $i = 1, 2, \ldots, M$ , the $i$ -th edge connects vertex $u_i$ and vertex $v_i$ bidirectionally.

Determine whether there is a way to paint each vertex black or white to satisfy both of the following conditions, and show one such way if it exists.

At least one vertex is painted black.
For every $i = 1, 2, \ldots, K$ , the following holds:
- the minimum distance between vertex $p_i$ and a vertex painted black is exactly $d_i$ .

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

Constraints

$1 \leq N \leq 2000$
$N-1 \leq M \leq \min\lbrace N(N-1)/2, 2000 \rbrace$
$1 \leq u_i, v_i \leq N$
$0 \leq K \leq N$
$1 \leq p_1 \lt p_2 \lt \cdots \lt p_K \leq N$
$0 \leq d_i \leq N$
The given graph is simple and connected.
All values in the input are integers.

Input

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

 $N$   $M$ 
 $u_1$   $v_1$ 
 $u_2$   $v_2$ 
 $\vdots$ 
 $u_M$   $v_M$ 
 $K$ 
 $p_1$   $d_1$ 
 $p_2$   $d_2$ 
 $\vdots$ 
 $p_K$   $d_K$

Output

If there is no way to paint each vertex black or white to satisfy the conditions, print No.
Otherwise, print Yes in the first line, and a string $S$ representing a coloring of the vertices in the second line, as shown below.
Here, $S$ is a string of length $N$ such that, for each $i = 1, 2, \ldots, N$ , the $i$ -th character of $S$ is $1$ if vertex $i$ is painted black and $0$ if white.

Yes
 $S$

If multiple solutions exist, you may print any of them.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

Yes
10100

One way to satisfy the conditions is to paint vertices $1, 3$ black and vertices $2, 4, 5$ white.
Indeed, for each $i = 1, 2, 3, 4, 5$ , let $A_i$ denote the minimum distance between vertex $i$ and a vertex painted black, and we have $(A_1, A_2, A_3, A_4, A_5) = (0, 1, 0, 1, 2)$ , where $A_1 = 0, A_5 = 2$ .

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

No

There is no way to satisfy the conditions by painting each vertex black or white, so you should print No.

Sample Input 3Copy

Copy

1 0
0

Sample Output 3Copy

Copy

Yes
1