結果
問題 |
No.3237 Find the Treasure!
|
ユーザー |
|
提出日時 | 2025-08-15 22:43:44 |
言語 | C# (.NET 8.0.404) |
結果 |
RE
|
実行時間 | - |
コード長 | 3,230 bytes |
コンパイル時間 | 7,940 ms |
コンパイル使用メモリ | 170,712 KB |
実行使用メモリ | 61,056 KB |
平均クエリ数 | 3.00 |
最終ジャッジ日時 | 2025-08-15 22:46:16 |
合計ジャッジ時間 | 23,999 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 1 |
other | RE * 22 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (128 ミリ秒)。 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; WriteLine(string.Join(" ", index)); 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(); } }