結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
|
提出日時 | 2018-11-05 15:47:52 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 81 ms / 2,000 ms |
コード長 | 1,951 bytes |
コンパイル時間 | 993 ms |
コンパイル使用メモリ | 113,920 KB |
実行使用メモリ | 8,576 KB |
最終ジャッジ日時 | 2024-06-13 01:54:41 |
合計ジャッジ時間 | 2,586 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;auto rdsp(){return readln.splitter;}void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}void readC(T...)(size_t n,ref T t){foreach(ref v;t)v=new typeof(v)(n);foreach(i;0..n){auto r=rdsp;foreach(ref v;t)pick(r,v[i]);}}void main(){int n, m, k; readV(n, m, k);int[] a, b, c; readC(m, a, b, c); --a[]; --b[];int[] e; readC(k, e); --e[];struct R { int a, b, c, i; }auto r = new R[](m);foreach (i; 0..m) r[i] = R(a[i], b[i], c[i], i);auto v = new bool[](m), uf = new UnionFind!int(n);foreach (ei; e) {uf.unite(r[ei].a, r[ei].b);v[ei] = true;}auto r2 = r.dup.sort!"a.c<b.c";foreach (ri; r2)if (!v[ri.i] && !uf.isSame(ri.a, ri.b)) {uf.unite(ri.a, ri.b);v[ri.i] = true;}auto s = 0L;foreach (i; 0..m)if (!v[i]) s += r[i].c;writeln(s);}struct UnionFind(T){import std.algorithm, std.range;T[] p; // parentconst T s; // sentinelconst T n;T countForests; // number of forestsT[] countNodes; // number of nodes in foreststhis(T n){this.n = n;s = n;p = new T[](n);p[] = s;countForests = n;countNodes = new T[](n);countNodes[] = 1;}T opIndex(T i){if (p[i] == s) {return i;} else {p[i] = this[p[i]];return p[i];}}bool unite(T i, T j){auto pi = this[i], pj = this[j];if (pi != pj) {p[pj] = pi;--countForests;countNodes[pi] += countNodes[pj];return true;} else {return false;}}auto countNodesOf(T i) { return countNodes[this[i]]; }bool isSame(T i, T j) { return this[i] == this[j]; }auto groups(){auto g = new T[][](n);foreach (i; 0..n) g[this[i]] ~= i;return g.filter!(l => !l.empty);}}