結果

問題 No.3237 Find the Treasure!
ユーザー GOTKAKO
提出日時 2025-08-15 21:57:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 337 ms / 3,000 ms
コード長 1,841 bytes
コンパイル時間 2,123 ms
コンパイル使用メモリ 210,304 KB
実行使用メモリ 25,972 KB
平均クエリ数 14.96
最終ジャッジ日時 2025-08-15 21:59:23
合計ジャッジ時間 10,899 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<pair<int,int>> UV(N-1);
    vector<vector<int>> Graph(N);
    for(int i=0; i<N-1; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        Graph.at(u).push_back(v);
        Graph.at(v).push_back(u);
        UV.at(i) = {u,v};
    }

    int query = 0;
    auto ask = [&](vector<int> X) -> bool {
        if(query == 15) assert(false);
        query++;
        cout << "?";
        for(int i=0; i<N-1; i++){
            cout << " ";
            cout << X.at(i)+1;
        }
        cout << endl;
        string ret; cin >> ret;
        if(ret == "Yes") return true;
        if(ret == "No") return false;
        assert(false);
    };

    vector<int> ord;
    vector<int> depth(N);
    {
        auto dfs = [&](auto dfs,int pos,int back,int dep) -> void {
            ord.push_back(pos); depth.at(pos) = dep;
            for(auto to : Graph.at(pos)) if(to != back) dfs(dfs,to,pos,dep^1); 
        };
        dfs(dfs,0,-1,0);
    }

    vector<int> X(N-1);
    for(int i=0; i<N-1; i++){
        auto [u,v] = UV.at(i);
        if(depth.at(u) == 0) X.at(i) = u;
        else X.at(i) = v;
    }
    bool even = ask(X);
    int low = 0,high = ord.size();
    while(high-low > 1){
        int mid = (high+low)/2;
        vector<bool> OK(N);
        for(int i=0; i<mid; i++){
            int pos = ord.at(i);
            if(even == (depth.at(pos) == 0)) OK.at(pos) = true;
        }
        for(int i=0; i<N-1; i++){
            auto [u,v] = UV.at(i);
            if(even != (depth.at(u) == 0)) swap(u,v);
            if(OK.at(u)) X.at(i) = u;
            else X.at(i) = v; 
        }
        if(ask(X)) high = mid;
        else low = mid;
    } 
    cout << "! " << ord.at(low)+1 << endl;
}
0