結果

問題 No.3237 Find the Treasure!
ユーザー tomerun
提出日時 2025-08-15 22:05:17
言語 Crystal
(1.14.0)
結果
AC  
実行時間 358 ms / 3,000 ms
コード長 1,078 bytes
コンパイル時間 16,662 ms
コンパイル使用メモリ 311,228 KB
実行使用メモリ 25,972 KB
平均クエリ数 13.83
最終ジャッジ日時 2025-08-15 22:05:44
合計ジャッジ時間 20,975 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

def query(a)
  puts "? #{a.map { |v| v + 1 }.join(" ")}"
  res = read_line
  if res == "Invalid"
    exit 1
  end
  return res == "Yes"
end

n = read_line.to_i
g = Array.new(n) { [] of Int32 }
es = Array.new(n - 1) do
  u, v = read_line.split.map { |v| v.to_i - 1 }
  g[u] << v
  g[v] << u
  {u, v}
end
q = [0]
depth = Array.new(n, -1)
parent = Array.new(n, -1)
depth[0] = 0
n.times do |i|
  cur = q[i]
  g[cur].each do |adj|
    next if parent[cur] == adj
    parent[adj] = cur
    depth[adj] = depth[cur] + 1
    q << adj
  end
end
q = es.map { |u, v| depth[u] % 2 == 0 ? u : v }.to_a
cands = [] of Int32
if query(q)
  cands = n.times.select { |i| depth[i] % 2 == 0 }.to_a
else
  cands = n.times.select { |i| depth[i] % 2 == 1 }.to_a
end
while cands.size > 1
  use = cands.first(cands.size // 2).to_set
  not_use = cands.last((cands.size + 1) // 2).to_set
  q = es.map { |u, v| use.includes?(u) || not_use.includes?(v) ? u : v }.to_a
  if query(q)
    cands.select! { |v| use.includes?(v) }
  else
    cands.reject! { |v| use.includes?(v) }
  end
end
puts "! #{cands[0] + 1}"
0