結果
問題 | No.317 辺の追加 |
ユーザー |
|
提出日時 | 2017-06-21 13:45:11 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 281 ms / 2,000 ms |
コード長 | 2,006 bytes |
コンパイル時間 | 1,445 ms |
コンパイル使用メモリ | 121,136 KB |
実行使用メモリ | 24,412 KB |
最終ジャッジ日時 | 2024-06-12 20:23:52 |
合計ジャッジ時間 | 9,054 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
import std.algorithm, std.conv, std.range, std.stdio, std.string;import std.container; // SList, DList, BinaryHeapimport std.typecons; // Tuple, Nullable, BigFlagsconst inf = 10 ^^ 6;void main(){auto rd1 = readln.split.to!(size_t[]), n = rd1[0], m = rd1[1];auto uf = UnionFind!size_t(n);foreach (_; 0..m) {auto rd2 = readln.split.to!(size_t[]), x = rd2[0]-1, y = rd2[1]-1;uf.unite(x, y);}auto si = new int[](n);foreach (i; 0..n) ++si[uf.find(i)];auto ti = si.filter!"a > 0".array.sort().group.array;auto dp = new int[](n+1), ma = 0;dp[1..$] = inf;foreach (t; ti) {auto u = t[0], v = t[1].to!int;auto dp2 = new int[](n+1);if (v <= 20) {foreach (k; 0..n+1) {dp2[k] = dp[k];foreach (j; 1..v+1) {if (k < u*j) break;dp2[k] = min(dp2[k], dp[k-u*j] + j);}}} else {foreach (k; 0..n.to!int+1)if (dp[k] < inf)dp[k] -= k/u;auto deqs = new DList!size_t[](u);foreach (k; 0..n.to!int+1) {auto deq = &deqs[k % u], mi = max(k - u*v, 0);while (!deq.empty && deq.front < mi) deq.removeFront();while (!deq.empty && dp[deq.back] >= dp[k]) deq.removeBack();deq.insertBack(k);dp2[k] = dp[deq.front] + k/u;}}dp = dp2;}foreach (r; dp[1..$]) writeln(r >= inf ? -1 : r-1);}struct UnionFind(T){import std.algorithm, std.range;T[] p; // parentconst T s; // sentinelconst T n;this(T n){this.n = n;p = new T[](n);s = n + 1;p[] = s;}T find(T i){if (p[i] == s) {return i;} else {p[i] = find(p[i]);return p[i];}}void unite(T i, T j){auto pi = find(i), pj = find(j);if (pi != pj) p[pj] = pi;}bool isSame(T i, T j) { return find(i) == find(j); }auto groups(){auto g = new T[][](n);foreach (i; 0..n) g[find(i)] ~= i;return g.filter!(l => !l.empty);}}