問題一覧 > 通常問題

No.1545 [Cherry 2nd Tune N] Anthem

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 45
作問者 : KazunKazun / テスター : Kanten4205Kanten4205
0 ProblemId : 6142 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-11 22:37:26

お知らせ

ジャッジの結果が QLE だった場合, 問題のミスまたはジャッジのミスが考えられます. ご報告をお願いします.

問題文

あなたは今, 曲を作ろうとしている. この曲の使われるフレーズの候補は $N$ 個であり, それぞれ フレーズ $1, \dots,$ フレーズ $N$ とする. フレーズ $i$ を歌うのには $X_i$ 秒を要する. ここで, 作ろうとしている曲に関して, 以下の条件を満たしていなければならない.

  • 曲の最初はフレーズ $S$, 最後はフレーズ $T$ でなくてはならない.
  • 曲に使われるフレーズの個数は最初の $S$ と最後の $T$ も含めて $K$ 個以上でなくてはならない. ただし, 同じフレーズを複数回用いている場合はその回数分カウントする.
  • 曲に使われているフレーズの個数を $R$ とし, $k~(1 \leq k \leq R)$ 番目のフレーズを $P_k$ とする. このとき, 全ての $1 \leq k < R$ に対して, $(P_k,P_{k+1})=(A_j, B_j)$ となる $1 \leq j \leq M$ が存在しなければならない.
そして, $1 \leq j \leq M$ に対して, フレーズ $A_j$ の歌い終わりから, フレーズ $B_j$ の歌い始めには $Y_j$ 秒要する.

上記の条件を全て満たすようにフレーズを組み立て, 曲を作ることは可能か? また, 可能ならば条件を満たすような曲について, 所要時間の総和の最小値を求め, それを達成する曲を1つ作れ. ここで, 所要時間とは, 各フレーズを歌うのに要する時間と, あるフレーズの歌い終わりから歌い始めに要する時間それぞれの総和である.

制約

  • $1 \leq N \leq 10^5$
  • $1 \leq S,T \leq N$
  • $1 \leq K \leq 3 \times 10^4$
  • $1 \leq X_i \leq 10^9$
  • $1 \leq M \leq \min (N^2, 2 \times 10^5) $
  • $1 \leq A_j, B_j \leq N$
  • $j \neq k$ ならば, $(A_j, B_j) \neq (A_k, B_k)$
  • $1 \leq Y_j \leq 10^9$
  • 以下の条件のうち, 少なくとも1つを満たしている. (2021/06/11 22:37 訂正 (一方→1つ))
    • [A] $1 \leq N \leq 10^5, 1 \leq K \leq 10$
    • [B] $1 \leq N, K \leq 130$
    • [C] $1 \leq N \leq 10, 1 \leq K \leq 3 \times 10^4$

入力

入力は以下の形式で標準入力から与えられる.
$N$ $S$ $T$ $K$
$X_1$ $\dots$ $X_N$
$M$
$A_1$ $B_1$ $Y_1$
$\vdots$
$A_M$ $B_M$ $Y_M$

出力

条件を満たすように曲を作ることが可能である場合, 1行目に Possible と出力し, 所要時間が最小であるような曲を2行目以降から以下のようにして出力せよ: 最短時間が $V$ で, それを達成するような曲が $R$ 個のフレーズからなり, $i$ 番目のフレーズが $P_i$ であるとき, 以下の形式で出力せよ.

$V$
$R$
$P_1$ $\dots$ $P_R$
このとき, 以下を満たしていなければならない.
  • $R \geq K$
  • $1 \leq P_i \leq N$
  • $P_1=S, P_R=T$
  • $1 \leq i < R$ に対して, $(P_i, P_{i+1})=(A_j, B_j)$ なる $1 \leq j \leq M$ が存在する.

もし, 不可能ならば,Impossibleと出力せよ. なお, 適する曲の作り方が複数考えられる場合, どれを出力しても良い.

最後に改行を忘れないこと.

サンプル

サンプル1
入力
3 1 3 3
5 7 6
5
1 1 2
1 2 1
1 3 3
2 3 4
3 3 1
出力
Possible
21
3
1 3 3

フレーズ $1, 3, 3$ という順番で構成される曲はフレーズ数 $3$ からなる曲であり, 所要時間は以下のように $5+3+6+1+6=21$ 秒である.

  • フレーズ $1$ を歌うのに $5$ 秒かかる.
  • フレーズ $1$ の歌い終わりから, フレーズ $3$ の歌い始めには $3$ 秒かかる.
  • フレーズ $3$ を歌うのに $6$ 秒かかる.
  • フレーズ $3$ の歌い終わりから, フレーズ $3$ の歌い始めには $1$ 秒かかる.
  • フレーズ $3$ を歌うのに $6$ 秒かかる.
なお, フレーズ $1, 1, 3$ という順番で構成される曲も条件を満たし, 所要時間も $21$ である. よって, 以下のような出力も正解になる.
Possible
21
3
1 1 3

サンプル2
入力
4 1 4 5
1 2 3 400
3
1 2 10
2 3 100
3 4 1000
出力
Impossible

$1, 2, 3, 4$ とフレーズ数が $4$ からなる曲は作れるが, $5$ 以上にすることは不可能である.

サンプル3
入力
6 3 2 1
3 3 3 3 3 3
6
3 2 1000000000
3 1 1
1 6 1
6 4 1
4 5 1
5 2 1
出力
Possible
23
6
3 1 6 4 5 2

フレーズ数が少ないことが曲の時間が短いことになるとは限らない.

サンプル4
入力
1 1 1 11
1
1
1 1 1
出力
Possible
21
11
1 1 1 1 1 1 1 1 1 1 1

このサンプルは [B], [C] は満たすが, [A] を満たさない.

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