QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#643189 | #7418. Interactive Vertex | 11d10xy | RE | 2ms | 9176kb | C++14 | 1.4kb | 2024-10-15 19:37:38 | 2024-10-15 19:37:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>G[200010];
namespace ds{
inline int ask(int x,vector<int>V){
printf("? %zu %d ",V.size(),x);
for(int u:V)printf("%d ",u);puts(""),fflush(stdout);
int w;scanf("%d",&w);
return w;
}
inline bool check(int u){return ask(u,G[u]);}
int sz[200010],mxsz[200010],N,rt;
bool vis[200010];
void dfs(int u,int fa){
sz[u]=1,mxsz[u]=0;
for(int v:G[u])if(v!=fa&&!vis[v]){
dfs(v,u),sz[u]+=sz[v],mxsz[u]=max(mxsz[u],sz[v]);
}
mxsz[u]=max(mxsz[u],N-sz[u]);
if(!rt||mxsz[u]<mxsz[rt])rt=u;
}
int find(vector<int>node){
int tot=0;
for(int u:node)tot+=sz[u];
tot=tot/2+1;
int i=0;
while(tot>=sz[node[i]]){
tot-=sz[node[i]],i++;
}
vector<int>L(begin(node),begin(node)+i),R(begin(node)+i,end(node));
if(ask(rt,L))return find(R);
else return find(L);
}
void solve(int u){
if(check(u)){
printf("! %d\n",u),fflush(stdout);
return;
}
vis[u]=true,rt=u;
vector<int>S;
for(int v:G[u])if(!vis[v])dfs(v,u),S.push_back(v);
sort(begin(S),end(S),[](int x,int y){return sz[x]<sz[y];});
int v=find(S);
rt=0,N=sz[v],dfs(v,0);
solve(rt);
}
}
int main(){
scanf("%d",&n);
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
G[u].push_back(v),G[v].push_back(u);
}
ds::N=n,ds::dfs(1,0);
ds::solve(ds::rt);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 9176kb
input:
5 1 2 1 3 1 4 1 5 1
output:
? 4 1 2 3 4 5 ! 1
result:
ok 1 queries
Test #2:
score: -100
Runtime Error
input:
5 1 2 1 3 1 4 1 5 0 0 0
output:
? 4 1 2 3 4 5 ? 3 1 2 3 4 ? 2 1 2 3