結果

問題 No.3237 Find the Treasure!
コンテスト
ユーザー ゼリトキ
提出日時 2025-08-15 22:13:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,692 bytes
コンパイル時間 2,875 ms
コンパイル使用メモリ 280,288 KB
実行使用メモリ 26,356 KB
平均クエリ数 14.43
最終ジャッジ日時 2025-08-15 22:13:26
合計ジャッジ時間 11,328 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 4 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define ll long long
const long long mod=998244353;
const long long hmod=46216567629137;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    int N;
    cin>>N;
    int u[N],v[N];
    vector<int>G[N+1];
    for(int i=1;i<=N-1;i++){
        cin>>u[i]>>v[i];
        G[u[i]].push_back(v[i]);
        G[v[i]].push_back(u[i]);
    }
    int l=1,r=N;
    bool already[N+1];
    while(l!=r){
        cout<<"? ";
        int m=(l+r)/2;
        for(int i=1;i<=N;i++) already[i]=1;
        for(int i=l;i<=m;i++) already[i]=0;
        int siz[N+1];
        for(int i=1;i<=N;i++) siz[i]=G[i].size();
        for(int i=1;i<=N-1;i++){
            if(already[u[i]]==0&&already[v[i]]==0){
                if(siz[u[i]]<siz[v[i]]){
                    already[u[i]]=1;
                    siz[v[i]]--;
                    cout<<u[i]<<" ";
                }
                else{
                    already[v[i]]=1;
                    siz[u[i]]--;
                    cout<<v[i]<<" ";
                }
            }
            else if(already[u[i]]==0){
                already[u[i]]=1;
                cout<<u[i]<<" ";
            }
            else if(already[v[i]]==0){
                already[v[i]]=1;
                cout<<v[i]<<" ";
            }
            else{
                cout<<v[i]<<" ";
            }
            
        }
        cout<<endl;
        string res;
        cin>>res;
        if(res=="Invalid"){
            while(true){

            }
            return 0;
        }
        if(res=="Yes") r=m;
        else l=m+1;
    }
    cout<<"! "<<l<<endl;
    return 0;
}
0