QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#396675 | #4926. Where Is the Root? | hos_lyric | 0 | 1ms | 4156kb | C++14 | 3.5kb | 2024-04-23 00:35:44 | 2024-04-23 00:35:44 |
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
int N;
vector<int> A, B;
int ask(const vector<int> &us) {
printf("? %d", (int)us.size());
for (const int u : us) {
printf(" %d", u + 1);
}
puts("");
fflush(stdout);
char str[10];
scanf("%s", str);
return !strcmp(str, "YES");
}
vector<vector<int>> graph;
vector<vector<int>> uss;
void dfs(int j, int u, int p) {
uss[j].push_back(u);
for (const int v : graph[u]) if (p != v) {
dfs(j, v, u);
}
}
int main() {
scanf("%d", &N);
A.resize(N - 1);
B.resize(N - 1);
for (int i = 0; i < N - 1; ++i) {
scanf("%d%d", &A[i], &B[i]);
--A[i];
--B[i];
}
graph.assign(N, {});
for (int i = 0; i < N - 1; ++i) {
graph[A[i]].push_back(B[i]);
graph[B[i]].push_back(A[i]);
}
int r = -1;
for (int u = 0; u < N; ++u) if (graph[u].size() >= 3) {
r = u;
break;
}
assert(~r);
const int len = graph[r].size();
uss.assign(len + 1, {});
uss[len].push_back(r);
for (int j = 0; j < len; ++j) {
dfs(j, graph[r][j], r);
}
auto vss = uss;
#define uss do_not_use_uss
for (int n = N; n > 2; ) {
const int half = (n + 1) / 2;
int lot = half;
vector<vector<int>> wss(len + 1);
for (int phase = 0; phase < 2; ++phase) {
for (int j = 0; j < len; ++j) {
int t = min((int)vss[j].size(), lot);
if (phase == 0) chmin(t, 1);
for (; t--; ) {
wss[j].push_back(vss[j].back());
vss[j].pop_back();
--lot;
}
}
}
vector<int> ws;
for (int j = 0; j < len; ++j) {
reverse(wss[j].begin(), wss[j].end());
ws.insert(ws.end(), wss[j].begin(), wss[j].end());
}
if (ask(ws)) {
vss.swap(wss);
n = half;
} else {
n -= half;
}
cerr<<"vss = "<<vss<<endl;
}
#undef uss
vector<int> cands;
for (int j = 0; j <= len; ++j) {
cands.insert(cands.end(), vss[j].rbegin(), vss[j].rend());
}
int ans = -1;
if (cands.size() == 1) {
ans = cands[0];
} else if (cands.size() == 2) {
for (int j = 0; j < len; ++j) if (!vss[j].size()) {
ans = ask({uss[j].back(), cands[0]}) ? cands[0] : cands[1];
break;
}
} else {
assert(false);
}
printf("! %d\n", ans + 1);
fflush(stdout);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 7
Accepted
time: 0ms
memory: 3832kb
input:
7 4 1 1 2 4 3 3 5 3 6 4 7 NO YES NO
output:
? 4 2 7 5 6 ? 2 4 1 ? 2 5 1 ! 4
result:
ok OK
Test #2:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
9 5 9 8 6 2 8 1 8 3 6 6 7 1 4 4 5 NO YES NO
output:
? 5 4 5 9 3 7 ? 2 2 1 ? 2 3 1 ! 2
result:
ok OK
Test #3:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
9 6 8 2 5 5 1 4 3 5 9 6 3 6 1 7 5 NO YES YES
output:
? 5 2 3 4 9 7 ? 2 6 8 ? 2 2 8 ! 8
result:
ok OK
Test #4:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
9 1 8 9 4 7 8 5 7 3 9 2 5 9 1 4 6 YES YES YES YES
output:
? 5 4 6 3 5 2 ? 3 6 3 2 ? 2 6 3 ? 2 2 6 ! 6
result:
ok OK
Test #5:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
9 7 1 8 4 2 8 5 2 2 3 1 2 1 9 9 6 YES YES YES NO
output:
? 5 7 4 5 3 6 ? 3 7 3 6 ? 2 7 3 ? 2 6 7 ! 3
result:
ok OK
Test #6:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
9 1 5 9 8 3 9 7 9 9 1 6 9 4 6 2 3 NO NO NO
output:
? 5 8 2 7 5 4 ? 2 3 1 ? 2 8 6 ! 9
result:
ok OK
Test #7:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
9 5 2 6 3 1 9 2 6 7 4 6 8 7 5 4 9 NO YES NO
output:
? 5 3 4 9 1 8 ? 2 5 7 ? 2 3 7 ! 5
result:
ok OK
Test #8:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
9 7 9 7 8 4 2 5 6 9 1 2 8 3 5 4 5 YES NO NO
output:
? 5 6 3 7 9 1 ? 3 6 3 1 ? 2 6 9 ! 7
result:
ok OK
Test #9:
score: 0
Accepted
time: 1ms
memory: 3876kb
input:
9 3 2 8 9 8 5 5 2 4 6 9 1 6 7 3 6 YES NO YES
output:
? 5 4 7 8 9 1 ? 3 4 7 1 ? 2 4 9 ! 9
result:
ok OK
Test #10:
score: -7
Wrong Answer
time: 1ms
memory: 3884kb
input:
9 5 6 3 9 5 9 3 4 2 4 7 6 4 8 7 1 NO YES NO
output:
? 5 6 7 1 2 8 ? 2 9 5 ? 2 2 5 ! 9
result:
wrong output format Unexpected end of file - int32 expected
Subtask #2:
score: 0
Wrong Answer
Test #24:
score: 10
Accepted
time: 1ms
memory: 3828kb
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 YES YES NO NO
output:
? 15 15 21 6 8 18 2 4 7 28 3 11 20 23 19 14 ? 8 8 18 2 4 20 23 19 14 ? 4 2 4 20 23 ? 2 2 4 ? 2 2 20 ! 23
result:
ok OK
Test #25:
score: 0
Accepted
time: 1ms
memory: 4120kb
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 NO YES NO YES NO
output:
? 15 6 8 10 3 21 11 19 2 24 13 22 4 9 27 18 ? 8 23 16 30 29 25 17 28 14 ? 4 23 25 17 28 ? 2 29 14 ? 2 8 29 ! 14
result:
ok OK
Test #26:
score: -10
Wrong Answer
time: 1ms
memory: 3888kb
input:
30 19 7 14 27 22 18 15 19 1 18 27 23 21 28 19 24 25 10 27 3 23 7 9 26 20 4 7 9 12 19 6 19 23 17 18 5 5 8 21 25 10 30 9 1 5 29 2 7 12 10 11 6 4 10 26 13 5 16 NO YES YES YES NO
output:
? 15 28 30 4 20 6 11 23 27 14 3 17 2 8 29 16 ? 8 7 19 15 24 12 10 25 21 ? 4 12 10 25 21 ? 2 25 21 ? 2 8 21 ! 25
result:
wrong output format Unexpected end of file - int32 expected
Subtask #3:
score: 0
Wrong Answer
Test #54:
score: 83
Accepted
time: 0ms
memory: 3864kb
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:
? 250 243 419 133 47 338 440 461 395 37 470 460 411 247 181 457 407 114 244 187 305 166 266 312 52 72 471 459 382 415 178 250 456 267 158 190 396 397 386 466 148 307 240 235 48 418 448 479 68 149 472 452 324 332 35 164 270 71 443 433 255 112 36 281 365 141 62 107 354 60 228 74 55 217 82 59 111 439 4...
result:
ok OK
Test #55:
score: 0
Wrong Answer
time: 0ms
memory: 4156kb
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:
? 250 150 104 343 32 110 170 487 3 414 254 297 218 86 405 185 377 259 66 289 231 271 500 417 369 268 161 442 441 299 97 59 359 44 422 177 489 63 386 51 74 327 344 48 266 409 400 273 339 153 73 367 58 261 215 491 173 138 376 226 112 132 124 398 275 443 107 256 296 94 196 319 115 230 260 303 345 283 3...
result:
wrong output format Unexpected end of file - int32 expected