QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#643189#7418. Interactive Vertex11d10xyRE 2ms9176kbC++141.4kb2024-10-15 19:37:382024-10-15 19:37:38

Judging History

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

  • [2024-10-15 19:37:38]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:9176kb
  • [2024-10-15 19:37:38]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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 

result: