問題一覧 > 通常問題

No.1477 Lamps on Graph

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 181
作問者 : nok0 / テスター : fairy_lettuce 👑 ygussany PCTprobability むかで
13 ProblemId : 5872 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-04-16 20:06:58

問題文

頂点に 1 から N まで、辺に 1 から M までの番号がついた N 頂点 M 辺からなる単純無向グラフが与えられます。辺 i は頂点 ui と頂点 vi を双方向に結んでいます。

このグラフの各頂点 i にはある整数 Ai が書かれています。

また、各頂点にはランプが置いてあり、最初は頂点 B1,B2,…,BK のランプのみが点灯しており、その他のランプは全て消灯しています。

あなたは以下の操作を 0 回以上任意の回数行うことができます。

  • 頂点を一つ選択する。(選択した頂点を x とする。) 頂点 x のランプの状態を切り替える。
  • その後、頂点 x と辺で結ばれた各頂点 y について、 Ax<Ay が満たされるならば頂点 y のランプの状態を切り替える。

    • ここでランプの状態を切り替えるとは、ランプが点灯しているならば消灯させ、消灯しているならば点灯させることを指します。

    操作によって全てのランプを消灯させることは可能でしょうか。もし可能な場合は操作回数が最小になる手順を一つ示してください。(出力形式の具体例は出力欄やサンプルを参考にしてください。)

    制約

    • 入力は全て整数である。
    • 1≤N≤105
    • 0≤M≤min(105,N(N−1)2)
    • 0≤Ai≤109
    • 1≤ui,vi≤N
    • 与えられるグラフは単純無向グラフである。
    • 1≤K≤N
    • 1≤B1<B2<⋯<BK≤N

    入力

    N M
A1 A2 … AN
u1 v1
u2 v2
⋮
uM vM
K
B1 B2 … BK

    出力

    全てのランプを消灯させることが不可能である場合、-1 と出力してください。

    可能である場合、以下の形式に従ってください。

    操作が Z 回からなるとき、以下のように Z+1 行にわたって出力してください。

    ここで xi は i 回目の操作で選択する頂点の番号です。

    Z
x1
x2
⋮
xZ

    サンプル

    サンプル1
    入力
    3 2
3 1 4
1 2
1 3
2
1 3
    出力
    1
1

    最初、頂点 1 と頂点 3 のランプが点灯しています。

    頂点 1 に対して操作を行うことを考えます。

    まず、頂点 1 のランプの状態が切り替わり、消灯します。

    頂点 1 と結ばれた頂点は頂点 2 と頂点 3 です。

    頂点 2 については、 A1=3,A2=1 より A1<A2 を満たさないので、頂点 2 のランプの状態は切り替わりません。

    頂点 3 については、 A1=3,A3=4 より A1<A3 を満たすので、頂点 3 のランプの状態が切り替わり、消灯します。

    よって、頂点 1 に対して操作を行うことで、 1 回で全てのランプを消灯させることができました。

    操作を行わないで全てのランプを消灯させることはできないので、これが操作の最小回数です。

    サンプル2
    入力
    3 0
100 200 300
3
1 2 3
    出力
    3
2
3
1

    グラフが連結でない場合もあることに注意してください。

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