A - 閉路グラフ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

下図のような n(n≧3) 頂点から成る閉路グラフがあります．

このグラフは，頂点 1 と頂点 2を結ぶ辺，頂点 2 と頂点 3，...，頂点 n-1 と頂点 n，そして頂点 n と頂点 1 を結ぶ辺から構成されています．

あなたは，このグラフからいくつかの頂点を取り除く(*)ことでグラフを分断し最終的に k 個の連結成分のみが残ったグラフにしたいと思っています． 実際に頂点を取り除き始める前に，そのような取り除き方が本当に存在するかどうかを判定してください．

(*) ある頂点を取り除くと，その頂点に直接繋がっている辺も取り除かれます．また，必要がなければ 1 つも頂点を取り除かなくても構いません．

入力

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

n
k
  • 1 行目には，閉路グラフの頂点の数を表す整数 n (3 ≦ n ≦ 10^5) が与えられる．
  • 2 行目には，残したい連結成分の数を表す整数 k (1 ≦ k ≦ 10^5) が与えられる．

出力

1行目に，n 頂点の閉路グラフからいくつかの頂点を取り除いて，ちょうど k 個の連結成分を含むグラフにすることができるならば YES，そうでないならば NO を出力せよ．最後に改行を忘れないこと．

入力例1

6
2

出力例1

YES

例えば，下図のように，頂点 1 と頂点 3 を取り除くことで，ちょうど 2 つの連結成分を残すことができます．

入力例2

3
2

出力例2

NO

入力のグラフは下図の通りです．どのように頂点を取り除いても 2 つの連結成分のみを残すことは出来ません．

入力例3

11
6

出力例3

NO

入力例4

11
5

出力例4

YES
B - ツリーグラフ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

n 頂点から成るツリーグラフがあります．このグラフはちょうど n-1 本の辺からなり，連結であることが保障されています．このような性質を持つグラフは必ず閉路を持ちません． 各頂点番号は 1 から n の相異なる整数で表され，辺のコストは全て 1 です．

このグラフのいくつかの頂点には宝石が高々 1 つあります．宝石のある頂点にいるときのみ，その宝石を回収することができます． あなたは，とある頂点 x から出発し，全ての宝石を回収し再び頂点 x に戻ってくるような経路のうち，最短のものを求めたいと思っています．そのような経路の長さを求めなさい．経路の長さは，経路に含まれる辺のコストの総和で定義されます．

入力

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

n x
h_1 h_2 … h_n
a_1 b_1
a_2 b_2
:
a_{n-1} b_{n-1}
  • 1 行目には，ツリーグラフの頂点の数を表す整数 n (1 ≦ n ≦ 100) と出発する頂点番号 x (1≦ x ≦n) が与えられる．
  • 2 行目には，頂点 i に存在する宝石の数を表す整数 h_i (0≦h_i≦1) が n 個，スペース区切りで与えられる．
  • 3 行から n-1 行，ツリーグラフの i 番目の辺が繋いでいる頂点の番号 a_i と b_i (1≦a_i,b_i≦n) が与えられる．
  • 与えられるグラフに自己辺や多重辺は存在せず，連結であることが保障されている．

出力

1 行目に，求める最短経路長を出力せよ．改行を忘れないこと．

入力例1

5 1
1 0 1 0 1
1 2
2 3
2 4
1 5

出力例1

6

入力のグラフと，それに対する最短経路の一例は下図の通りです．x=1 なので頂点 1 から出発しています．

入力例2

3 2
0 1 0
1 2
2 3

出力例2

0

出発地点にのみ宝石があるので，移動しないのが最短です．

C - 有向グラフ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

n 個の頂点と m 本の辺から成る有向グラフがあります．n 個の頂点は， 1 から n の相異なる整数で番号付けされています． 各頂点には，a から z のアルファベットが 1 つ書かれています．

あなたはこのグラフを好きな頂点から開始し，各頂点を任意の順番で訪問することで，ちょうど k 個のアルファベットを回収したいです． 頂点は何度も訪問することができ，その頂点にアルファベットが存在する場合は任意の訪問タイミングで回収することが出来ますが，アルファベットは一度回収すると無くなります．必要がなければ，回収しなくても良いです．

あなたは，ただ回収するだけでは退屈であると思ったので，それらの k 個のアルファベットを回収した順番に並べたときに辞書順最小になるように回収することにしました．

そのような回収方法を行ったときの，k 個のアルファベットを，回収した順番に出力しなさい． k 個のアルファベットを回収する方法が存在しない場合は，-1 を出力しなさい．

入力

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

n m k
c_1 c_2 … c_n
a_1 b_1
a_2 b_2
:
a_{m} b_{m}
  • 1 行目には，グラフの頂点の数を表す整数 n (1 ≦ n ≦ 300) と 辺の数を表す整数 m (0 ≦ m ≦ 1000) と回収したいアルファベットの数を表す整数 k (1≦k≦n) が与えられる．
  • 2 行目には，頂点 i に書かれているアルファベット c_i( a から z の小文字アルファベット) が n 個，スペース区切りで与えられる．
  • 3 行から m 行，グラフの i 番目の有向辺が繋いでいる頂点の番号 a_i と b_i (1≦a_i,b_i≦n) が与えられる． これは，i 番目の辺が，a_i から b_i に移動できる有向辺であることを表す．
  • 与えられるグラフに自己辺や多重辺は存在しないが，逆辺は存在することがある．また，連結であることは保障されていない．

出力

1 行目に，辞書順最小となるように回収した k 個のアルファベットを，回収した順番に出力せよ．k 個のアルファベットを回収する方法が存在しない場合は，-1 を出力せよ．最後に改行を忘れないこと．

入力例1

4 4 3
a b b a
1 2
2 3
3 1
4 3

出力例1

aab

この入出力例を説明する図は以下の通りとなります．頂点 4 → 3 → 1 → 2 と移動する過程で，頂点 4 の a，頂点 1 の a，そして頂点 2 の b を順番に回収することで辞書順最小の答えとなります．

入力例2

5 4 4
d a b c a
1 2
2 3
3 4
2 5

出力例2

dabc

入力例3

5 4 3
d a b c a
1 2
2 3
3 4
2 5

出力例3

abc

入力例4

3 0 2
a b c

出力例4

-1

3 つの頂点は孤立しており，どの頂点から開始しても，ちょうど 2 個のアルファベットを回収することはできません．

D - グラフではない

Time Limit: 5 sec / Memory Limit: 750 MB

問題文

長さ N の数列 X={x_1,x_2,...,x_N} があります．この列に Q 回のクエリ操作を行うことを考えます．クエリ操作は3 種類あり，以下の通りです．

  • 1 a b v ― 数列 X の区間 [a,b] に一様に値 v を加える．
  • 2 a b c d ― 数列 X の区間 [a,b] を，クエリが呼ばれた時点での区間 [c,d] の値に書き換える．b-a=d-c が保障されている．より厳密には，このクエリによって得られる数列を X' とおくと，X'_{a}=X_c，X'_{a+1}=X_{c+1}，…，X'_{b}=X_{d} となる．[a,b] に含まれない j について，X'_j=X_j となる．
  • 3 a b ― 数列 X の区間 [a,b] に含まれる値の総和を求める．

あなたは，このようなクエリを順番に処理するプログラムを書かなくてはなりません．

入力

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

N Q
x_1 x_2 … x_N
Query_1
Query_2
:
Query_Q
  • 1 行目には，数列 X の長さを表す整数 N (1 ≦ N ≦ 2×10^5) とクエリの数を表す整数 Q (1 ≦ Q ≦ 2×10^5) が与えられる．
  • 2 行目には，数列 X の i 番目の要素の値 x_i (-10^6 ≦ x_i ≦ 10^6) がスペース区切りで N 個与えられる．
  • 3 行目から Q 行，問題文中で説明したクエリが，1 a b v， 2 a b c d もしくは 3 a b の形式で与えられる．-10^6 ≦ v ≦ 10^6，1 ≦ a ≦ b ≦ N，1 ≦ c ≦ d ≦ N，b-a = d-cであることが保障されている．

出力

3 a b の形式のクエリに対し，与えられた順番に答えを出力せよ．出力毎に改行を行うこと．

入力例1

5 5
1 2 3 4 5
3 1 5
1 1 3 1
3 1 3
2 1 3 2 4
3 1 5

出力例1

15
9
20
  • 1 つ目のクエリは，[1,5] の総和を出力するクエリであり，1+2+3+4+5=15 を出力します．
  • 2 つ目のクエリは，[1,3] に一様に 1 を足すクエリであり，この操作を行った後，X={2,3,4,4,5} となります．
  • 3 つ目のクエリは，[1,3] の総和を求めるクエリであり，2+3+4=9 を出力します．
  • 4 つ目のクエリは，[2,4] の値を [1,3] にコピーするクエリであり，この操作を行った後，X={3,4,4,4,5} となります．
  • 5 つ目のクエリは，[1,5] の総和を求めるクエリであり，3+4+4+4+5=20 を出力します．

入力例2

10 30
-5 -5 -2 -1 2 -2 0 -4 2 5
2 9 10 9 10
2 3 5 2 4
1 2 10 -1
2 1 7 1 7
3 1 4
2 1 6 2 7
2 5 8 6 9
3 4 8
3 1 10
3 9 9
1 3 8 -1
2 4 9 1 6
3 2 7
1 9 10 -4
1 6 9 -5
1 4 6 -7
3 2 5
2 10 10 7 7
1 3 4 -10
3 4 9
3 8 9
2 6 7 8 9
3 3 5
3 3 9
1 2 10 -10
2 4 6 4 6
2 4 9 5 10
1 2 6 7
3 7 8
1 3 6 3

出力例2

-20
-8
-18
1
-29
-36
-78
-18
-50
-86
-38