結果
問題 | No.2642 Don't cut line! |
ユーザー | tobisatis |
提出日時 | 2024-02-19 22:24:30 |
言語 | C# (.NET 8.0.203) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,919 bytes |
コンパイル時間 | 15,075 ms |
コンパイル使用メモリ | 157,824 KB |
実行使用メモリ | 184,668 KB |
最終ジャッジ日時 | 2024-02-20 12:47:32 |
合計ジャッジ時間 | 29,482 ms |
ジャッジサーバーID (参考情報) |
judge16 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 567 ms
71,424 KB |
testcase_02 | AC | 564 ms
71,556 KB |
testcase_03 | AC | 566 ms
75,140 KB |
testcase_04 | AC | 561 ms
72,068 KB |
testcase_05 | AC | 565 ms
77,316 KB |
testcase_06 | AC | 431 ms
60,160 KB |
testcase_07 | AC | 439 ms
60,160 KB |
testcase_08 | AC | 431 ms
60,160 KB |
testcase_09 | AC | 434 ms
60,284 KB |
testcase_10 | AC | 436 ms
60,292 KB |
testcase_11 | AC | 427 ms
60,292 KB |
testcase_12 | AC | 439 ms
60,292 KB |
testcase_13 | AC | 429 ms
60,164 KB |
testcase_14 | AC | 434 ms
60,292 KB |
testcase_15 | AC | 455 ms
60,292 KB |
testcase_16 | AC | 498 ms
62,716 KB |
testcase_17 | AC | 501 ms
65,316 KB |
testcase_18 | AC | 533 ms
70,916 KB |
testcase_19 | AC | 426 ms
73,032 KB |
testcase_20 | AC | 368 ms
58,276 KB |
testcase_21 | AC | 402 ms
59,556 KB |
testcase_22 | AC | 401 ms
65,744 KB |
testcase_23 | AC | 543 ms
70,912 KB |
testcase_24 | AC | 315 ms
54,692 KB |
testcase_25 | AC | 333 ms
55,716 KB |
testcase_26 | AC | 407 ms
59,556 KB |
testcase_27 | AC | 380 ms
65,956 KB |
testcase_28 | AC | 517 ms
75,136 KB |
testcase_29 | AC | 385 ms
58,532 KB |
testcase_30 | AC | 346 ms
56,740 KB |
testcase_31 | AC | 445 ms
71,148 KB |
testcase_32 | AC | 359 ms
57,252 KB |
testcase_33 | AC | 85 ms
33,316 KB |
testcase_34 | AC | 85 ms
33,316 KB |
testcase_35 | AC | 83 ms
184,668 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (104 ms)。 MSBuild のバージョン 17.7.3+8ec440e68 (.NET) main -> /home/judge/data/code/bin/Release/net7.0/main.dll main -> /home/judge/data/code/bin/Release/net7.0/publish/
ソースコード
namespace AtCoder; #nullable enable using System.Numerics; 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 size, int edges)[] Verticals { get; set; } public UnionFind(int verticals) { Verticals = new (int, int, int)[verticals]; for (int i = 0; i < verticals; i++) Verticals[i] = (i, 1, 0); } public int Union(int x, int y) { (x, y) = (Find(x), Find(y)); if (Size(x) < Size(y)) (x, y) = (y, x); Verticals[x].edges += 1; if (x == y) return x; Verticals[x].edges += Verticals[y].edges; Verticals[x].size += Verticals[y].size; Verticals[y].parent = x; return x; } public int Find(int x) => Parent(x).parent; public int Size(int x) => Parent(x).size; public int Edges(int x) => Parent(x).edges; (int parent, int size, int edges) Parent(int x) { var parentId = Verticals[x].parent; if (parentId == x) return Verticals[x]; var parent = Parent(parentId); Verticals[x].parent = parent.parent; return parent; } } class AtCoder { object? Solve() { var n = Int(); var k = Int(); var c = Input<long>(); var edges = new (int, int, int, int, bool)[k]; for (var i = 0; i < k; i++) { var u = Int() - 1; var v = Int() - 1; var w = Int(); var p = Int(); edges[i] = (w, p, u, v, false); } Array.Sort(edges); var ans = 0L; var minC = 0L; var uf = new UnionFind(n); var g = n.Repeat(() => new List<(int, int)>()); for (var i = 0; i < k; i++) { var (w, p, u, v, _) = edges[i]; if (uf.Find(u) != uf.Find(v)) { minC += w; uf.Union(u, v); edges[i].Item5 = true; g[u].Add((v, w)); g[v].Add((u, w)); ans = Math.Max(ans, p); } } if (minC > c) return -1; var f = new long[n]; void S(int v, int prev) { foreach (var (next, nw) in g[v]) { if (next == prev) continue; f[next] = Math.Max(f[next], nw); S(next, v); } } S(edges[0].Item3, -1); foreach (var (w, p, u, v, t) in edges) { if (t) continue; var max = Math.Max(f[u], f[v]); if (minC - max + w < c) ans = Math.Max(ans, p); } return ans; } public static void Main() => new AtCoder().Run(); public void Run() { var res = Solve(); if (res != null) { if (res is bool yes) res = yes ? "Yes" : "No"; sw.WriteLine(res); } sw.Flush(); } string[] input = Array.Empty<string>(); int iter = 0; readonly StreamWriter sw = new(Console.OpenStandardOutput()) { AutoFlush = false }; #pragma warning disable IDE0051 string String() { while (iter >= input.Length) (input, iter) = (Console.ReadLine()!.Split(' '), 0); return input[iter++]; } T Input<T>() where T : IParsable<T> => T.Parse(String(), null); int Int() => Input<int>(); void Out(object? x, string? separator = null) { separator ??= Environment.NewLine; if (x is System.Collections.IEnumerable obj and not string) { var firstLine = true; foreach (var item in obj) { if (!firstLine) sw.Write(separator); firstLine = false; sw.Write(item); } } else sw.Write(x); sw.WriteLine(); } #pragma warning restore IDE0051 }