QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#115543 | #4926. Where Is the Root? | jamielim | 0 | 8ms | 3768kb | C++14 | 3.1kb | 2023-06-26 11:26:54 | 2023-06-26 11:26:57 |
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;
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);
}
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);
}
findFakeRoot();
dfs(fr,0);
int l=0,r=maxdep;
while(l<r){
int m=(l+r+1)/2;
vector<int> v;
for(int i=1;i<=n;i++){
if(dep[i]>=m)v.pb(i);
}
if(query(v))l=m;
else r=m-1;
}
if(l==0){
printf("! %d\n",fr);
fflush(stdout);
return 0;
}
vector<int> v,perm;
for(int i=1;i<=n;i++)if(dep[i]==l)v.pb(i);
if(SZ(v)==1){
printf("! %d\n",v[0]);
fflush(stdout);
return 0;
}
while(SZ(v)>2){
int m=(SZ(v)+1)/2;
vector<int> q;
for(int i=0;i<m;i++){
q.pb(v[i]);
}
for(int i:perm)q.pb(i);
if(query(q)){
for(int i=m;i<SZ(v);i++)perm.pb(v[i]);
while(SZ(v)>m)v.pop_back();
}else{
for(int i=0;i<m;i++)perm.pb(v[i]);
vector<int> tmp;
for(int i=m;i<SZ(v);i++)tmp.pb(v[i]);
v=tmp;
}
}
vector<int> l0=getOtherLeaves(v[0]);
vector<int> l1=getOtherLeaves(v[1]);
int ans=v[0];
if(SZ(l0)>=2){
l0.pb(v[0]);
if(query(l0)){
ans=v[0];
}else{
ans=v[1];
}
}else{
l1.pb(v[1]);
if(query(l1)){
ans=v[1];
}else{
ans=v[0];
}
}
printf("! %d\n",ans);
printf("! %d\n",ans);
fflush(stdout);
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 7
Accepted
time: 0ms
memory: 3724kb
input:
7 4 1 1 2 4 3 3 5 3 6 4 7 NO
output:
? 6 1 2 3 5 6 7 ! 4
result:
ok OK
Test #2:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
9 5 9 8 6 2 8 1 8 3 6 6 7 1 4 4 5 YES NO YES YES
output:
? 6 2 3 5 6 7 9 ? 3 3 7 9 ? 2 2 5 ? 4 2 3 7 9 ! 2 ! 2
result:
ok OK
Test #3:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
9 6 8 2 5 5 1 4 3 5 9 6 3 6 1 7 5 NO YES NO YES
output:
? 5 2 4 5 7 9 ? 8 1 2 3 4 5 7 8 9 ? 2 1 3 ? 5 2 4 7 8 9 ! 8 ! 8
result:
ok OK
Test #4:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
9 1 8 9 4 7 8 5 7 3 9 2 5 9 1 4 6 YES YES YES
output:
? 6 2 3 4 5 6 9 ? 4 2 3 4 6 ? 1 6 ! 6
result:
ok OK
Test #5:
score: -7
Wrong Answer
time: 1ms
memory: 3684kb
input:
9 7 1 8 4 2 8 5 2 2 3 1 2 1 9 9 6 NO YES YES YES
output:
? 4 4 6 7 9 ? 8 1 3 4 5 6 7 8 9 ? 2 1 3 ? 4 1 3 4 5 ! 1 ! 1
result:
wrong output format Unexpected end of file - int32 expected
Subtask #2:
score: 0
Wrong Answer
Test #24:
score: 10
Accepted
time: 0ms
memory: 3692kb
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 YES NO NO YES NO YES
output:
? 23 2 3 5 6 7 8 9 10 11 12 13 16 17 18 20 21 22 23 24 25 28 29 30 ? 12 2 3 5 9 11 12 16 17 18 25 28 29 ? 6 6 7 8 10 13 20 ? 9 6 7 8 10 13 20 21 22 23 ? 10 6 7 8 10 13 20 21 22 24 30 ? 17 2 4 6 9 10 11 12 14 16 17 19 20 21 23 24 25 28 ! 23 ! 23
result:
ok OK
Test #25:
score: -10
Wrong Answer
time: 1ms
memory: 3768kb
input:
30 15 16 8 6 19 2 26 17 30 15 26 4 1 6 1 23 15 1 29 25 21 3 12 1 2 24 29 22 9 1 3 10 27 28 5 12 20 5 14 7 5 26 7 18 10 23 1 28 3 11 7 1 19 23 13 23 29 30 YES NO YES NO YES
output:
? 22 2 3 4 5 8 10 11 13 14 16 17 18 19 20 21 22 24 25 26 27 29 30 ? 12 2 3 4 11 17 20 21 22 24 25 26 29 ? 5 5 8 10 13 14 ? 8 5 8 10 16 18 19 27 30 ? 15 4 8 9 11 13 14 16 17 18 20 21 22 24 25 27 ! 13 ! 13
result:
wrong output format Unexpected end of file - int32 expected
Subtask #3:
score: 0
Wrong Answer
Test #54:
score: 66
Acceptable Answer
time: 6ms
memory: 3700kb
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:
? 306 2 6 7 8 9 13 14 15 16 19 24 26 27 29 30 31 34 35 36 37 39 40 42 44 47 48 50 52 53 55 56 57 59 60 62 63 67 68 70 72 74 75 77 78 79 80 82 85 86 87 88 91 94 95 97 98 103 107 108 109 111 112 113 114 118 119 120 121 122 126 127 128 129 131 134 135 136 138 140 141 142 144 145 146 148 149 150 151 153...
result:
points 0.79518072290 OK
Test #55:
score: 83
Accepted
time: 8ms
memory: 3716kb
input:
500 188 321 193 4 334 269 259 66 121 396 73 153 332 477 263 67 178 262 185 377 175 53 462 245 390 337 387 200 445 92 387 159 135 263 323 312 143 374 252 47 375 382 303 345 345 283 150 1 66 289 462 82 317 201 169 423 154 193 486 251 368 305 357 375 107 443 437 348 64 55 408 465 315 469 186 328 197 39...
output:
? 240 3 5 8 9 10 14 17 19 20 21 22 24 27 30 31 34 36 39 40 43 45 46 47 49 50 54 55 56 57 60 64 65 67 68 69 70 71 72 76 77 78 79 84 87 88 89 90 91 92 95 96 101 102 103 106 108 113 114 116 117 119 120 122 123 125 128 129 130 131 135 137 139 140 141 147 148 151 152 154 157 158 160 162 167 169 171 172 1...
result:
ok OK
Test #56:
score: 63
Acceptable Answer
time: 0ms
memory: 3668kb
input:
500 423 179 253 294 3 58 24 345 129 8 428 443 349 246 15 286 367 428 272 290 294 230 144 239 403 270 354 110 17 157 441 227 216 226 220 211 199 353 397 445 204 269 234 452 283 355 58 375 500 400 284 11 388 235 385 21 53 124 77 290 395 235 71 351 300 26 109 326 462 215 87 405 116 196 430 136 481 390 ...
output:
? 279 2 6 8 9 12 15 17 18 19 24 25 26 28 29 30 34 35 37 41 42 43 45 46 49 51 53 56 57 60 63 64 68 72 74 75 76 78 79 80 81 82 84 85 86 87 89 90 91 95 96 98 99 100 101 102 106 109 110 112 113 114 115 116 117 118 119 120 121 124 125 126 127 128 129 130 131 132 136 137 138 139 140 141 142 143 144 146 14...
result:
points 0.75903614460 OK
Test #57:
score: 0
Wrong Answer
time: 5ms
memory: 3636kb
input:
500 246 390 321 345 385 319 393 475 36 188 453 174 35 111 420 55 411 304 78 250 483 12 241 37 295 498 348 52 105 329 321 255 222 272 457 247 262 189 239 31 114 489 45 321 269 380 493 340 287 128 248 33 201 388 12 379 231 65 94 241 85 43 262 391 154 156 92 140 58 117 44 166 284 480 290 44 157 393 32 ...
output:
? 306 4 5 6 7 9 10 13 15 17 18 19 20 23 25 26 28 29 30 34 37 38 39 40 41 45 46 49 50 51 54 57 59 60 61 62 63 67 68 69 75 76 78 79 80 83 84 85 89 90 91 92 94 95 96 99 101 102 103 104 105 107 109 110 112 115 116 117 119 121 122 123 125 126 127 128 130 132 133 134 138 139 140 141 145 147 149 151 155 15...
result:
wrong output format Unexpected end of file - int32 expected