結果
問題 |
No.3087 University Coloring
|
ユーザー |
|
提出日時 | 2025-04-04 22:00:09 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 335 ms / 2,000 ms |
コード長 | 3,608 bytes |
コンパイル時間 | 9,812 ms |
コンパイル使用メモリ | 170,676 KB |
実行使用メモリ | 189,008 KB |
最終ジャッジ日時 | 2025-04-04 22:00:30 |
合計ジャッジ時間 | 20,040 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (106 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
#nullable enable using System.Numerics; void Run() { var n = Int(); var m = Int(); var edges = new (int, int, int)[m]; for (var i = 0; i < m; i++) { var a = Int() - 1; var b = Int() - 1; var c = Int(); edges[i] = (-c, a, b); } Array.Sort(edges); var uf = new UnionFind(n); var ans = 0L; foreach (var (nc, a, b) in edges) { var c = -nc; if (uf.Find(a) != uf.Find(b)) { ans += c; uf.Union(a, b); } } Out(ans * 2); } #region AtCoderIO _io_; var _backend_ = new StandardIOBackend(); _io_ = new(){ Backend = _backend_ }; Run(); _backend_.Flush(); string String() => _io_.Next(); int Int() => int.Parse(String()); void Out(object? x, string? sep = null) => _io_.Out(x, sep); class AtCoderIO { public required StandardIOBackend Backend { get; init; } Memory<string> _input = Array.Empty<string>(); int _iter = 0; public string Next() { while (_iter >= _input.Length) (_input, _iter) = (Backend.ReadLine().Split(' '), 0); return _input.Span[_iter++]; } public void Out(object? x, string? separator = null) { if (x == null) return; separator ??= Environment.NewLine; if (x is System.Collections.IEnumerable a and not string) { var objects = a.Cast<object>(); if (separator == Environment.NewLine && !objects.Any()) return; x = string.Join(separator, objects); } Backend.WriteLine(x); } } class StandardIOBackend { readonly StreamReader _sr = new(Console.OpenStandardInput()); readonly StreamWriter _sw = new(Console.OpenStandardOutput()) { AutoFlush = false }; public string ReadLine() => _sr.ReadLine()!; public void WriteLine(object? value) => _sw.WriteLine(value); public void Flush() => _sw.Flush(); } #endregion static class Extensions { public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray(); } class UnionFind { (int parent, int edgeCount)[] Verticals { get; set; } bool EnabledUndo { get; init; } Stack<(int v, (int parent, int edges))> Histories { get; init; } public UnionFind(int verticals, bool enableUndo = false) { Verticals = new (int, int)[verticals]; for (int i = 0; i < verticals; i++) Verticals[i] = (-1, 0); Histories = new(); EnabledUndo = enableUndo; } public int Union(int x, int y) { (x, y) = (Find(x), Find(y)); var (sx, sy) = (Size(x), Size(y)); if (sx < sy) (x, y, sy) = (y, x, sx); var (nx, ny) = (Verticals[x], Verticals[y]); Histories.Push((x, nx)); Histories.Push((y, ny)); if (x == y) nx.edgeCount += 1; else { ny.parent = x; nx.parent -= sy; nx.edgeCount += ny.edgeCount + 1; } (Verticals[y], Verticals[x]) = (ny, nx); return x; } public int Find(int x) { var pid = Verticals[x].parent; if (pid < 0) return x; var aid = Find(pid); if (!EnabledUndo) Verticals[x].parent = aid; return aid; } public int Size(int x) => -Verticals[Find(x)].parent; public int EdgeCount(int x) => Verticals[Find(x)].edgeCount; public bool Undo() { if (!EnabledUndo || Histories.Count == 0) return false; for (var i = 0; i < 2; i++) { var (v, h) = Histories.Pop(); Verticals[v] = h; } return true; } }