結果
問題 |
No.3237 Find the Treasure!
|
ユーザー |
|
提出日時 | 2025-08-15 22:47:42 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 401 ms / 3,000 ms |
コード長 | 3,185 bytes |
コンパイル時間 | 7,648 ms |
コンパイル使用メモリ | 171,584 KB |
実行使用メモリ | 57,728 KB |
平均クエリ数 | 14.43 |
最終ジャッジ日時 | 2025-08-15 22:48:28 |
合計ジャッジ時間 | 18,191 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (103 ミリ秒)。 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[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).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 n = NN; var map = NMap(n - 1); 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 color = new int[n]; color[0] = 1; DFS(0, tree, color); var plus = new List<int>(); var minus = new List<int>(); for (var i = 0; i < n; ++i) { if (color[i] > 0) plus.Add(i); else minus.Add(i); } var q = new List<int>(n - 1); for (var i = 0; i < n - 1; ++i) { if (color[map[i][0]] == 1) q.Add(map[i][0]); else q.Add(map[i][1]); } List<int> target; if (Query(q)) target = plus; else target = minus; var ans = new bool[n]; foreach (var ti in target) ans[ti] = true; var index = Enumerable.Repeat(-1, n).ToArray(); for (var i = 0; i < target.Count; ++i) index[target[i]] = i; for (var b = 1; b < target.Count; b *= 2) { var nq = new List<int>(n - 1); for (var i = 0; i < n - 1; ++i) { if (index[map[i][0]] >= 0) { if ((index[map[i][0]] & b) == 0) nq.Add(map[i][0]); else nq.Add(map[i][1]); } else { if ((index[map[i][1]] & b) == 0) nq.Add(map[i][1]); else nq.Add(map[i][0]); } } if (Query(nq)) { for (var i = 0; i < target.Count; ++i) if ((i & b) != 0) ans[target[i]] = false; } else { for (var i = 0; i < target.Count; ++i) if ((i & b) == 0) ans[target[i]] = false; } } for (var i = 0; i < n; ++i) if (ans[i]) WriteLine($"! {i + 1}"); } static void DFS(int cur, List<int>[] tree, int[] color) { foreach (var next in tree[cur]) { if (color[next] != 0) continue; color[next] = -color[cur]; DFS(next, tree, color); } } static bool Query(List<int> q) { WriteLine($"? {string.Join(" ", q.Select(qi => qi + 1))}"); var s = ReadLine(); if (s == "Yes") return true; else if (s == "No") return false; throw new Exception(); } }