| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1220385 | mariamtsagareli | Easter Eggs (info1cup17_eastereggs) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int q(vector<int>& v) {
cout<<"? "<<v.size();
for(int x : v) cout<<" "<<x;
cout<<"\n"<<flush;
int r;
cin>>r;
return r;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n; cin>>n;
vector<vector<int>> g(n+1);
for (int i=1,u,v; i<n; i++) {
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> s(n+1,1),z(n+1),p(n+1);
vector<int> t;
function<int(int,int)>d=[&](int u,int par){
p[u]=par;
z[u]=1;
t.push_back(u);
for (int w: g[u]) if(w!=par&&s[w])z[u]+=d(w,u);
return z[u];
};
function<int()> f=[&]() {
t.clear();
int r=1;
while (!s[r]) r++;
d(r,0);
int m=t.size();
for (int u: t) {
int mx=m-z[u];
for (int w: g[u]) if(w!=p[u] && s[w]) mx=max(mx,z[w]);
if (mx*2<=m) return u;
}
return t[0];
};
function<void(int,int,vector<int>&)> e=[&](int u,int par,vector<int>& c) {
c.push_back(u);
for (int w: g[u]) if(w!=par && s[w]) e(w,u,c);
};
while(1){
vector<int> c;
for (int i=1;i<=n;i++) if(s[i]) c.push_back(i);
if (c.size()==1) {
cout<<"! "<<c[0]<<"\n"<<flush;
break;
}
int u=f();
if (q(*(new vector<int>{u}))) {
cout<<"! "<<u<<"\n"<<flush;
break;
}
vector<vector<int>> a;
for (int w: g[u]) if(s[w]){
vector<int>v;
e(w,u,v);
a.push_back(v);
}
int l=0,
r=a.size();
while(r-l>1) {
int m=(l+r)/2;
vector<int> v={u};
for (int i=l;i<m;i++) for (int x: a[i]) v.push_back(x);
if (q(v)) r=m; else l=m;
}
vector<int> k=a[l];
s.assign(n+1,0);
for (int x:k) s[x]=1;
}
return 0;
}