結果
問題 | No.2726 Rooted Tree Nim |
ユーザー | kakel-san |
提出日時 | 2024-04-23 23:11:33 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 468 ms / 2,000 ms |
コード長 | 1,769 bytes |
コンパイル時間 | 11,353 ms |
コンパイル使用メモリ | 166,660 KB |
実行使用メモリ | 232,224 KB |
最終ジャッジ日時 | 2024-11-06 05:31:50 |
合計ジャッジ時間 | 18,560 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 63 ms
30,448 KB |
testcase_01 | AC | 331 ms
56,576 KB |
testcase_02 | AC | 370 ms
85,180 KB |
testcase_03 | AC | 455 ms
83,924 KB |
testcase_04 | AC | 468 ms
83,916 KB |
testcase_05 | AC | 375 ms
84,740 KB |
testcase_06 | AC | 375 ms
84,476 KB |
testcase_07 | AC | 413 ms
87,628 KB |
testcase_08 | AC | 413 ms
88,632 KB |
testcase_09 | AC | 321 ms
75,896 KB |
testcase_10 | AC | 324 ms
80,540 KB |
testcase_11 | AC | 385 ms
89,056 KB |
testcase_12 | AC | 397 ms
89,840 KB |
testcase_13 | AC | 313 ms
232,224 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (97 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static int[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray(); static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray(); public static void Main() { Solve(); } static void Solve() { var t = NN; var ans = new bool[t]; for (var u = 0; u < t; ++u) { var c = NList; var (n, k) = (c[0], c[1]); var map = NMap(n - 1); var a = NList; ans[u] = Rooted(n, k, map, a); } WriteLine(string.Join("\n", ans.Select(f => f ? "K" : "P"))); } static bool Rooted(int n, int k, int[][] map, int[] a) { var tree = new List<int>[n]; for (var i = 0; i < tree.Length; ++i) tree[i] = new List<int>(); foreach (var edge in map) { tree[edge[0]].Add(edge[1]); tree[edge[1]].Add(edge[0]); } var len = Enumerable.Repeat(int.MaxValue / 2, n).ToArray(); len[0] = 0; var q = new Queue<int>(); q.Enqueue(0); while (q.Count > 0) { var cur = q.Dequeue(); foreach (var next in tree[cur]) { if (len[next] <= len[cur] + 1) continue; len[next] = len[cur] + 1; q.Enqueue(next); } } var g = 0; for (var i = 0; i < n; ++i) if (len[i] % 2 == 1) g ^= a[i] % (k + 1); return g != 0; } }