問題一覧 > 通常問題

No.1477 Lamps on Graph

レベル : / AI推定難易度 : 1050 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （AC するまで非表示） / 解いたユーザー数 186
作問者 : nok0 / テスター : fairy_lettuce ygussany PCTprobability むかで
お気に入りにしたユーザー ProblemId : 5872 / 自分の提出
問題文最終更新日: 2021-04-16 20:06:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 291 (順位表) の他の問題:

Problem Statement

You are given a simple undirected graph with $N$ vertices and $M$ edges, where the vertices are numbered from $1$ to $N$ and the edges are numbered from $1$ to $M$. Edge $i$ connects vertex $u_i$ and vertex $v_i$ bidirectionally.

Each vertex $i$ of this graph has an integer $A_i$ written on it.

Also, a lamp is placed on each vertex. Initially, only the lamps on vertices $B_1,B_2,\dots,B_K$ are on, and all other lamps are off.

You may perform the following operation any number of times, possibly $0$ times.

  • Choose one vertex. (Let $x$ be the chosen vertex.) Toggle the state of the lamp on vertex $x$.
  • Then, for each vertex $y$ connected to vertex $x$ by an edge, if $A_x < A_y$ is satisfied, toggle the state of the lamp on vertex $y$.

    • Here, toggling the state of a lamp means turning it off if it is on, and turning it on if it is off.

    Is it possible to turn off all the lamps by the operations? If it is possible, show one procedure that minimizes the number of operations. (For concrete examples of the output format, refer to the Output section and the samples.)

    Constraints

    • All inputs are integers.
    • $1 \le N\le 10^5$
    • $0 \le M\le \mathrm{min}(10^5, \frac{N(N-1)}{2})$
    • $0 \le A_i \le 10^9$
    • $1 \le u_i, v_i \le N $
    • The given graph is a simple undirected graph.
    • $1 \le K \le N$
    • $1 \le B_1 < B_2 < \dots < B_K \le N$

    Input

    $N\ M$
$A_1\ A_2\ \dots\ A_N$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_M\ v_M$
$K$
$B_1\ B_2\ \dots\ B_K$

    Output

    If it is impossible to turn off all the lamps, print -1.

    If it is possible, follow the format below.

    When the procedure consists of $Z$ operations, print $Z+1$ lines as follows.

    Here, $x_i$ is the number of the vertex chosen in the $i$-th operation.

    $Z$
$x_1$
$x_2$
$\vdots$
$x_Z$

    Sample

    Sample 1
    Input
    3 2
3 1 4
1 2
1 3
2
1 3
    Output
    1
1

    Initially, the lamps on vertex $1$ and vertex $3$ are on.

    Consider performing the operation on vertex $1$.

    First, the state of the lamp on vertex $1$ is toggled, and it turns off.

    The vertices connected to vertex $1$ are vertex $2$ and vertex $3$.

    For vertex $2$, since $A_1 = 3,A_2=1$, $A_1 < A_2$ is not satisfied, so the state of the lamp on vertex $2$ is not toggled.

    For vertex $3$, since $A_1 = 3,A_3=4$, $A_1 < A_3$ is satisfied, so the state of the lamp on vertex $3$ is toggled, and it turns off.

    Therefore, by performing the operation on vertex $1$, all the lamps could be turned off in $1$ operation.

    Since it is impossible to turn off all the lamps without performing any operation, this is the minimum number of operations.

    Sample 2
    Input
    3 0
100 200 300
3
1 2 3
    Output
    3
2
3
1

    Note that the graph may not be connected.

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。