結果

問題 No.3237 Find the Treasure!
ユーザー Moss_Local
提出日時 2025-08-15 22:37:54
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 5,943 bytes
コンパイル時間 12,837 ms
コンパイル使用メモリ 397,564 KB
実行使用メモリ 26,240 KB
平均クエリ数 12.57
最終ジャッジ日時 2025-08-15 22:38:27
合計ジャッジ時間 21,696 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable does not need to be mutable
   --> src/main.rs:120:9
    |
120 |     let mut vec: Vec<i64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
   --> src/main.rs:126:9
    |
126 |     let mut vec: Vec<i64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:131:9
    |
131 |     let mut vec: Vec<usize> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:137:9
    |
137 |     let mut vec: Vec<f64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:142:9
    |
142 |     let mut vec: Vec<char> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:147:9
    |
147 |     let mut vec: Vec<usize> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:153:9
    |
153 |     let mut vec: Vec<i64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

ソースコード

diff # 

// -*- coding:utf-8-unix -*-
// #![feature(map_first_last)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
// use core::num;
use std::cmp::*;
use std::fmt::*;
use std::hash::*;
use std::io::BufRead;
use std::iter::FromIterator;
use std::*;
use std::{cmp, collections, fmt, io, iter, ops, str};
const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const LINF: i64 = 2147483647;
const INF128: i128 = 1223372036854775807000000000000;
const MOD1: i64 = 1000000007;
const MOD9: i64 = 998244353;
const MOD: i64 = MOD9;
// const MOD: i64 = MOD2;
const UMOD: usize = MOD as usize;
const M_PI: f64 = 3.14159265358979323846;
const NINF: i64 = -(1i64 << 60);

// use proconio::input;
// const MOD: i64 = INF;

use cmp::Ordering::*;
use std::collections::*;

use std::io::stdin;
use std::io::stdout;
use std::io::Write;

macro_rules! p {
    ($x:expr) => {
        //if expr
        println!("{}", $x);
    };
}

macro_rules! vp {
    // vector print separate with space
    ($x:expr) => {
        println!(
            "{}",
            $x.iter()
                .map(|x| x.to_string())
                .collect::<Vec<_>>()
                .join(" ")
        );
    };
}

macro_rules! d {
    ($x:expr) => {
        eprintln!("{:?}", $x);
    };
}
macro_rules! yn {
    ($val:expr) => {
        if $val {
            println!("Yes");
        } else {
            println!("No");
        }
    };
}

macro_rules! map{
    // declear btreemap
    ($($key:expr => $val:expr),*) => {
        {
            let mut map = ::std::collections::BTreeMap::new();
            $(
                map.insert($key, $val);
            )*
            map
        }
    };
}

macro_rules! set{
    // declear btreemap
    ($($key:expr),*) => {
        {
            let mut set = ::std::collections::BTreeSet::new();
            $(
                set.insert($key);
            )*
            set
        }
    };
}

//input output
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_mat<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

#[allow(dead_code)]
fn readii() -> (i64, i64) {
    let mut vec: Vec<i64> = read_vec();
    (vec[0], vec[1])
}

#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
    let mut vec: Vec<i64> = read_vec();
    (vec[0], vec[1], vec[2])
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
    let mut vec: Vec<usize> = read_vec();
    (vec[0], vec[1])
}

#[allow(dead_code)]
fn readff() -> (f64, f64) {
    let mut vec: Vec<f64> = read_vec();
    (vec[0], vec[1])
}

fn readcc() -> (char, char) {
    let mut vec: Vec<char> = read_vec();
    (vec[0], vec[1])
}

fn readuuu() -> (usize, usize, usize) {
    let mut vec: Vec<usize> = read_vec();
    (vec[0], vec[1], vec[2])
}

#[allow(dead_code)]
fn readiiii() -> (i64, i64, i64, i64) {
    let mut vec: Vec<i64> = read_vec();
    (vec[0], vec[1], vec[2], vec[3])
}

fn rot(v: &[i64; 8], k: usize) -> [i64; 8] {
    let mut r = [0; 8];
    for i in 0..8 {
        r[i] = v[(i + k) % 8];
    }
    r
}

#[derive(Copy, Clone)]
struct E {
    u: usize,
    v: usize,
}
fn dfs_sz(
    u: usize,
    p: isize,
    g: &Vec<Vec<usize>>,
    in_set: &Vec<i32>,
    sz: &mut Vec<usize>,
) -> usize {
    let mut s = if in_set[u] != -1 { 1 } else { 0 };
    for &nv in &g[u] {
        if nv as isize != p {
            s += dfs_sz(nv, u as isize, g, in_set, sz);
        }
    }
    sz[u] = s;
    s
}
fn build_half(
    u: usize,
    p: isize,
    mut need: usize,
    g: &Vec<Vec<usize>>,
    sz: &Vec<usize>,
    in_set: &mut Vec<i32>,
) {
    if need == 0 {
        return;
    }
    in_set[u] = 1;
    need -= 1;
    for &nv in &g[u] {
        if nv as isize != p && need > 0 {
            let take = std::cmp::min(sz[nv], need);
            if take > 0 {
                build_half(nv, u as isize, take, g, sz, in_set);
                need -= take;
            }
        }
    }
}
fn main() {
    let n: usize = read();
    let mut edges = vec![E { u: 0, v: 0 }; n - 1];
    let mut g = vec![vec![]; n];
    for i in 0..n - 1 {
        let (mut u, mut v) = readuu();
        u -= 1;
        v -= 1;
        edges[i] = E { u, v };
        g[u].push(v);
        g[v].push(u);
    }
    let mut cand: Vec<usize> = (0..n).collect();
    for _ in 0..15 {
        if cand.len() <= 1 {
            break;
        }
        let mut in_set = vec![-1; n];
        for &v in &cand {
            in_set[v] = 0;
        }
        let mut sz = vec![0; n];
        dfs_sz(cand[0], -1, &g, &in_set, &mut sz);
        let target = cand.len() / 2;
        build_half(cand[0], -1, target, &g, &sz, &mut in_set);
        let mut x = vec![0; n - 1];
        for i in 0..n - 1 {
            let (u, v) = (edges[i].u, edges[i].v);
            if in_set[u] == 1 {
                x[i] = u + 1;
            } else {
                x[i] = v + 1;
            }
        }
        print!("?");
        for val in &x {
            print!(" {}", val);
        }
        println!();
        stdout().flush().unwrap();
        let s: String = read();
        if s == "Yes" {
            let mut nxt = vec![];
            for &v in &cand {
                if in_set[v] == 1 {
                    nxt.push(v);
                }
            }
            cand = nxt;
        } else if s == "No" {
            let mut nxt = vec![];
            for &v in &cand {
                if in_set[v] != 1 {
                    nxt.push(v);
                }
            }
            cand = nxt;
        } else {
            return;
        }
    }
    println!("! {}", cand[0] + 1);
    stdout().flush().unwrap();
}
0