QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#643182#7418. Interactive Vertex11d10xyWA 2ms9088kbC++141.4kb2024-10-15 19:35:462024-10-15 19:35:47

Judging History

你现在查看的是最新测评结果

  • [2024-10-15 19:35:47]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9088kb
  • [2024-10-15 19:35:46]
  • 提交

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("? %d %zu ",x,V.size());
   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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 9088kb

input:

5
1 2
1 3
1 4
1 5

1

output:

? 1 4 2 3 4 5 
! 1

result:

wrong answer invalid format