QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#115559 | #4926. Where Is the Root? | jamielim | 0 | 5ms | 3708kb | C++14 | 2.3kb | 2023-06-26 11:45:28 | 2023-06-26 11:45:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef long long ll;
typedef unsigned long long ull;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const ll MOD=1000000007;
int n;
vector<int> adj[505];
int dist[2][505];
int fr;
int dep[505];
int maxdep;
vector<int> leaf;
bool lf[505];
void findFakeRoot(){
for(int i=1;i<=n;i++)dist[0][i]=dist[1][i]=INF;
dist[0][1]=0;
queue<int> q;
q.push(1);
int maxi=1;
while(!q.empty()){
int cur=q.front();q.pop();
for(int i:adj[cur]){
if(dist[0][i]>dist[0][cur]+1){
dist[0][i]=dist[0][cur]+1;
q.push(i);
if(dist[0][i]>dist[0][maxi])maxi=i;
}
}
}
dist[1][maxi]=0;
q.push(maxi);
while(!q.empty()){
int cur=q.front();q.pop();
for(int i:adj[cur]){
if(dist[1][i]>dist[1][cur]+1){
dist[1][i]=dist[1][cur]+1;
q.push(i);
if(dist[1][i]>dist[1][maxi])maxi=i;
}
}
}
fr=maxi;
while(dist[1][fr]>dist[1][maxi]/2){
for(int i:adj[fr]){
if(dist[1][i]==dist[1][fr]-1){
fr=i;break;
}
}
}
}
void dfs(int x,int p){
maxdep=max(maxdep,dep[x]);
int c=0;
for(int i:adj[x]){
if(i==p)continue;
dep[i]=dep[x]+1;
dfs(i,x);
c++;
}
if(c==0){
leaf.pb(x);
lf[x]=1;
}
}
vector<int> t;
void dfs2(int x,int p,int avoid){
int c=0;
for(int i:adj[x]){
if(i==p)continue;
if(i==avoid)continue;
dfs2(i,x,avoid);
c++;
}
if(c==0)t.pb(x);
}
vector<int> getOtherLeaves(int x){
t.clear();
dfs2(fr,0,x);
return t;
}
bool query(vector<int> v){
sort(ALL(v));
v.resize(unique(ALL(v))-v.begin());
printf("? %d",SZ(v));
for(int i:v)printf(" %d",i);
printf("\n");
fflush(stdout);
char str[5];
scanf("%s",str);
if(str[0]=='Y')return 1;
return 0;
}
int main(){
scanf("%d",&n);
int a,b;
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
adj[a].pb(b);adj[b].pb(a);
}
for(int i=1;i<=n;i++){
if(SZ(adj[i])>=3){
dfs(fr,0);
break;
}
}
for(int i=1;i<=n;i++){
if(!lf[i]){
leaf.pb(i);
if(query(leaf)){
printf("! %d\n",i);
fflush(stdout);
return 0;
}else leaf.pop_back();
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3672kb
input:
7 4 1 1 2 4 3 3 5 3 6 4 7
output:
? 2 0 1
result:
wrong output format Unexpected end of file - int32 expected
Subtask #2:
score: 0
Wrong Answer
Test #24:
score: 0
Wrong Answer
time: 2ms
memory: 3708kb
input:
30 1 15 29 30 1 4 7 28 29 17 1 26 26 7 12 5 27 13 3 7 27 1 21 15 9 22 22 5 24 27 19 1 25 30 22 27 6 15 16 13 18 2 27 10 27 30 20 26 8 15 18 8 14 1 27 23 11 3
output:
? 2 0 1
result:
wrong output format Unexpected end of file - int32 expected
Subtask #3:
score: 0
Wrong Answer
Test #54:
score: 0
Wrong Answer
time: 5ms
memory: 3696kb
input:
500 419 133 44 225 391 269 419 461 293 347 108 31 110 363 423 257 321 155 498 87 180 492 251 5 357 30 341 172 275 109 372 446 286 336 208 339 162 320 138 103 129 219 62 141 359 286 130 238 470 460 418 48 210 358 429 13 323 143 382 415 406 394 309 175 325 170 128 108 6 113 363 17 470 457 7 224 288 48...
output:
? 2 0 1
result:
wrong output format Unexpected end of file - int32 expected