Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 700 点
問題文
りんごさんは頂点に 1,2,...,N の番号がついた N 個の頂点と 1,2,...,M の番号がついた M 本の辺からなる無向グラフ G を持っています。 辺 i は頂点 a_{i} と b_{i} を双方向につなぐ長さ w_i の辺です。
現在、りんごさんはこれらの N 個の頂点を 1,2,...,K の番号がついた K 種類の色で彩色している途中です。頂点 i は色 c_i で塗られています。ただし、c_i = 0 ならば頂点 i にはまだ色が塗られていません。
りんごさんはまだ色が塗られていない全ての頂点を K 種類の色のいずれかでそれぞれ塗ったのち、すぬけくんに G をあげます。
すぬけくんは G を使って頂点に 1,2,...,K の番号がついた K 個の頂点と M 本の辺からなる無向グラフ G' を作ります。 はじめ、G' には辺がありません。i 番目の辺は以下のようにして追加されます。
- G の辺 i に着目したとき両端の頂点に塗られている色をそれぞれ x,y とする
- 頂点 x と y を双方向につなぐ長さ w_i の辺を G' に追加する
G' の最小全域木に含まれる辺の長さの総和としてありうる値は最小でいくつになりますか？りんごさんがどのように色を塗っても G' が連結にならない場合は -1 を出力してください。
制約
- 1 \leq N,M \leq 10^{5}
- 1 \leq K \leq N
- 0 \leq c_i \leq K
- 1 \leq a_i,b_i \leq N
- 1 \leq w_i \leq 10^{9}
- 与えられるグラフは単純とも連結とも限らない
- 与えられる入力は全て整数
部分点
- 100 点分のデータセットでは N=K,c_i = i が成立する
- 別の 100 点分のデータセットでは c_i \neq 0 が成立する
- 別の 200 点分のデータセットでは c_i = 0 が成立する
入力
入力は以下の形式で標準入力から与えられる。
N M K
c_1 c_2 ... c_{N}
a_1 b_1 w_1
:
a_M b_M w_M
出力
答えを出力せよ。
入力例 1
4 3 3 1 0 1 2 1 2 10 2 3 20 2 4 50
出力例 1
60
頂点 2 に色 3 を塗ったときのみ、G' が連結になります。
入力例 2
5 2 4 0 0 0 0 0 1 2 10 2 3 10
出力例 2
-1
どのようにりんごさんが色を塗っても、2 本の辺で 4 つの頂点が連結になるようにすることはできません。
入力例 3
9 12 9 1 2 3 4 5 6 7 8 9 6 9 9 8 9 6 6 7 85 9 5 545631016 2 1 321545 1 6 33562944 7 3 84946329 9 7 15926167 4 7 53386480 5 8 70476 4 6 4549 4 8 8
出力例 3
118901402
入力例 4
18 37 12 5 0 4 10 8 7 2 10 6 0 9 12 12 11 11 11 0 1 17 1 1 11 16 7575 11 15 9 10 10 289938980 5 10 17376 18 4 1866625 8 11 959154208 18 13 200 16 13 2 2 7 982223 12 12 9331 13 12 8861390 14 13 743 2 10 162440 2 4 981849 7 9 1 14 17 2800 2 7 7225452 3 7 85 5 17 4 2 13 1 10 3 45 1 15 973 14 7 56553306 16 17 70476 7 18 9 9 13 27911 18 14 7788322 11 11 8925 9 13 654295 2 10 9 10 1 545631016 3 4 5 17 12 1929 2 11 57 1 5 4 1 17 7807368
出力例 4
171
Score : 700 points
Problem Statement
Ringo has an undirected graph G with N vertices numbered 1,2,...,N and M edges numbered 1,2,...,M. Edge i connects Vertex a_{i} and b_{i} and has a length of w_i.
Now, he is in the middle of painting these N vertices in K colors numbered 1,2,...,K. Vertex i is already painted in Color c_i, except when c_i = 0, in which case Vertex i is not yet painted.
After he paints each vertex that is not yet painted in one of the K colors, he will give G to Snuke.
Based on G, Snuke will make another undirected graph G' with K vertices numbered 1,2,...,K and M edges. Initially, there is no edge in G'. The i-th edge will be added as follows:
- Let x and y be the colors of the two vertices connected by Edge i in G.
- Add an edge of length w_i connecting Vertex x and y in G'.
What is the minimum possible sum of the lengths of the edges in the minimum spanning tree of G'? If G' will not be connected regardless of how Ringo paints the vertices, print -1.
Constraints
- 1 \leq N,M \leq 10^{5}
- 1 \leq K \leq N
- 0 \leq c_i \leq K
- 1 \leq a_i,b_i \leq N
- 1 \leq w_i \leq 10^{9}
- The given graph may NOT be simple or connected.
- All input values are integers.
Partial Scores
- In the test set worth 100 points, N = K and c_i = i.
- In the test set worth another 100 points, c_i \neq 0.
- In the test set worth another 200 points, c_i = 0.
Input
Input is given from Standard Input in the following format:
N M K
c_1 c_2 ... c_{N}
a_1 b_1 w_1
:
a_M b_M w_M
Output
Print the answer.
Sample Input 1
4 3 3 1 0 1 2 1 2 10 2 3 20 2 4 50
Sample Output 1
60
G' will only be connected when Vertex 2 is painted in Color 3.
Sample Input 2
5 2 4 0 0 0 0 0 1 2 10 2 3 10
Sample Output 2
-1
Regardless of how Ringo paints the vertices, two edges is not enough to connect four vertices as one.
Sample Input 3
9 12 9 1 2 3 4 5 6 7 8 9 6 9 9 8 9 6 6 7 85 9 5 545631016 2 1 321545 1 6 33562944 7 3 84946329 9 7 15926167 4 7 53386480 5 8 70476 4 6 4549 4 8 8
Sample Output 3
118901402
Sample Input 4
18 37 12 5 0 4 10 8 7 2 10 6 0 9 12 12 11 11 11 0 1 17 1 1 11 16 7575 11 15 9 10 10 289938980 5 10 17376 18 4 1866625 8 11 959154208 18 13 200 16 13 2 2 7 982223 12 12 9331 13 12 8861390 14 13 743 2 10 162440 2 4 981849 7 9 1 14 17 2800 2 7 7225452 3 7 85 5 17 4 2 13 1 10 3 45 1 15 973 14 7 56553306 16 17 70476 7 18 9 9 13 27911 18 14 7788322 11 11 8925 9 13 654295 2 10 9 10 1 545631016 3 4 5 17 12 1929 2 11 57 1 5 4 1 17 7807368
Sample Output 4
171
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 900 点
問題文
すぬけくんは (0,1,2, ...,N-1) を並び替えて得られるような数列 p を持っています。 p の (0-indexedでの) i 番目の数は p_i です。
すぬけくんは 1,2,...,N-1 の番号がついた N-1 種類の操作を自由な順番で何度でも行うことができます。 k 番の操作を行うと以下のソースコードで表されるような処理が実行されます。
for(int i=k;i<N;i++)
swap(p[i],p[i-k]);
すぬけくんは操作を 0 回以上 10^{5} 回以下行って p を昇順に並び替えたいです。そのような操作手順の一例を示してください。 なお、この問題の制約下で、そのような操作手順が必ず存在することが証明できます。
制約
- 2 \leq N \leq 200
- 0 \leq p_i \leq N-1
- p は (0,1,2,...,N-1) を並び替えて得られる
部分点
- 300 点分のデータセットでは N \leq 7 が成立する
- 別の 400 点分のデータセットでは N \leq 30 が成立する
入力
入力は以下の形式で標準入力から与えられる。
N
p_0 p_1 ... p_{N-1}
出力
操作回数(これを m とする)を 1 行目に出力せよ。 続く m 行のうち i 行目には i 番目に実行する操作の番号を出力せよ。 m が 10^5 以下であり、m 回の操作後に p が昇順となっていれば正解となる。
入力例 1
5 4 2 0 1 3
出力例 1
4 2 3 1 2
- 以下の図に各操作による p の変化を示します。
入力例 2
9 1 0 4 3 5 6 2 8 7
出力例 2
11 3 6 1 3 5 2 4 7 8 6 3
Score : 900 points
Problem Statement
Snuke has a sequence p, which is a permutation of (0,1,2, ...,N-1). The i-th element (0-indexed) in p is p_i.
He can perform N-1 kinds of operations labeled 1,2,...,N-1 any number of times in any order. When the operation labeled k is executed, the procedure represented by the following code will be performed:
for(int i=k;i<N;i++)
swap(p[i],p[i-k]);
He would like to sort p in increasing order using between 0 and 10^{5} operations (inclusive). Show one such sequence of operations. It can be proved that there always exists such a sequence of operations under the constraints in this problem.
Constraints
- 2 \leq N \leq 200
- 0 \leq p_i \leq N-1
- p is a permutation of (0,1,2,...,N-1).
Partial Scores
- In the test set worth 300 points, N \leq 7.
- In the test set worth another 400 points, N \leq 30.
Input
Input is given from Standard Input in the following format:
N
p_0 p_1 ... p_{N-1}
Output
Let m be the number of operations in your solution. In the first line, print m. In the i-th of the following m lines, print the label of the i-th executed operation. The solution will be accepted if m is at most 10^5 and p is in increasing order after the execution of the m operations.
Sample Input 1
5 4 2 0 1 3
Sample Output 1
4 2 3 1 2
- Each operation changes p as shown below:
Sample Input 2
9 1 0 4 3 5 6 2 8 7
Sample Output 2
11 3 6 1 3 5 2 4 7 8 6 3