QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#396676 | #4926. Where Is the Root? | hos_lyric | 7 | 4ms | 4136kb | C++14 | 3.6kb | 2024-04-23 00:40:40 | 2024-04-23 00:40:40 |
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;
vector<int> ls;
#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;
}
}
}
auto ws = ls;
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 {
ls.insert(ls.end(), ws.begin(), ws.end());
n -= half;
}
cerr<<"vss = "<<vss<<", ls = "<<ls<<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: 7
Accepted
Test #1:
score: 7
Accepted
time: 1ms
memory: 3840kb
input:
7 4 1 1 2 4 3 3 5 3 6 4 7 NO YES NO
output:
? 4 2 7 5 6 ? 6 2 7 5 6 4 1 ? 2 5 1 ! 4
result:
ok OK
Test #2:
score: 0
Accepted
time: 1ms
memory: 3888kb
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 ? 7 4 5 9 3 7 2 1 ? 2 3 1 ! 2
result:
ok OK
Test #3:
score: 0
Accepted
time: 1ms
memory: 3832kb
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 ? 7 2 3 4 9 7 6 8 ? 2 2 8 ! 8
result:
ok OK
Test #4:
score: 0
Accepted
time: 1ms
memory: 3828kb
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: 3784kb
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: 0ms
memory: 4124kb
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 ? 7 8 2 7 5 4 3 1 ? 2 8 6 ! 9
result:
ok OK
Test #7:
score: 0
Accepted
time: 1ms
memory: 3832kb
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 ? 7 3 4 9 1 8 5 7 ? 2 3 7 ! 5
result:
ok OK
Test #8:
score: 0
Accepted
time: 1ms
memory: 4116kb
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: 3828kb
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: 0
Accepted
time: 1ms
memory: 4136kb
input:
9 5 6 3 9 5 9 3 4 2 4 7 6 4 8 7 1 NO NO YES
output:
? 5 6 7 1 2 8 ? 7 6 7 1 2 8 9 5 ? 2 2 3 ! 3
result:
ok OK
Test #11:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
9 8 3 7 9 4 3 9 4 5 2 9 6 2 1 8 5 NO YES NO
output:
? 5 7 5 2 1 6 ? 7 7 5 2 1 6 3 8 ? 2 7 8 ! 3
result:
ok OK
Test #12:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
9 8 1 1 5 7 1 1 3 1 4 6 1 1 9 2 1 NO NO NO
output:
? 5 8 5 7 3 4 ? 7 8 5 7 3 4 6 9 ? 2 8 2 ! 1
result:
ok OK
Test #13:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
9 8 1 2 1 9 1 1 3 1 4 1 7 6 1 5 1 YES NO NO
output:
? 5 8 2 9 3 4 ? 3 8 2 9 ? 2 8 3 ! 4
result:
ok OK
Test #14:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
9 6 1 1 3 1 9 2 1 1 8 1 4 7 1 5 1 YES YES YES YES
output:
? 5 6 3 9 2 8 ? 3 6 3 9 ? 2 6 3 ? 2 9 6 ! 6
result:
ok OK
Test #15:
score: 0
Accepted
time: 1ms
memory: 4112kb
input:
9 4 1 1 6 3 1 1 9 2 1 1 7 1 8 1 5 NO NO YES
output:
? 5 4 6 3 9 2 ? 7 4 6 3 9 2 7 8 ? 2 4 5 ! 5
result:
ok OK
Test #16:
score: 0
Accepted
time: 1ms
memory: 3900kb
input:
9 8 1 1 7 1 9 6 1 3 1 4 1 1 2 5 1 YES YES YES NO
output:
? 5 8 7 9 6 3 ? 3 8 7 9 ? 2 8 7 ? 2 9 8 ! 7
result:
ok OK
Test #17:
score: 0
Accepted
time: 1ms
memory: 4124kb
input:
9 3 5 8 2 8 7 6 1 8 3 9 2 5 1 6 4 YES YES YES NO
output:
? 5 2 9 7 6 4 ? 3 9 7 4 ? 2 9 7 ? 2 4 9 ! 7
result:
ok OK
Test #18:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
9 2 5 5 4 9 2 6 3 3 9 7 4 1 9 6 8 YES YES YES NO
output:
? 5 5 4 7 8 1 ? 3 7 8 1 ? 2 7 8 ? 2 1 7 ! 8
result:
ok OK
Test #19:
score: 0
Accepted
time: 1ms
memory: 4116kb
input:
9 7 9 7 5 8 4 1 7 6 2 4 2 9 6 3 5 YES YES YES YES
output:
? 5 2 4 8 3 1 ? 3 8 3 1 ? 2 8 3 ? 2 1 8 ! 8
result:
ok OK
Test #20:
score: 0
Accepted
time: 1ms
memory: 4088kb
input:
9 9 7 1 8 2 7 4 5 1 9 6 8 5 2 8 3 YES YES NO
output:
? 5 2 5 4 6 3 ? 3 4 6 3 ? 2 4 6 ! 3
result:
ok OK
Test #21:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
9 4 9 7 5 1 7 1 3 5 8 1 9 6 4 2 6 YES YES YES NO
output:
? 5 7 5 8 3 2 ? 3 8 3 2 ? 2 8 3 ? 2 2 8 ! 3
result:
ok OK
Test #22:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
9 5 3 6 4 5 2 4 9 7 2 9 7 1 3 8 3 YES YES NO
output:
? 5 9 4 6 1 8 ? 3 6 1 8 ? 2 6 1 ! 8
result:
ok OK
Test #23:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
9 8 2 9 3 6 1 8 5 3 4 7 8 4 1 2 6 YES YES YES NO
output:
? 5 4 3 9 5 7 ? 3 9 5 7 ? 2 9 5 ? 2 7 9 ! 5
result:
ok OK
Subtask #2:
score: 0
Wrong Answer
Test #24:
score: 10
Accepted
time: 0ms
memory: 3844kb
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: -10
Wrong Answer
time: 0ms
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
output:
? 15 6 8 10 3 21 11 19 2 24 13 22 4 9 27 18 ? 23 6 8 10 3 21 11 19 2 24 13 22 4 9 27 18 23 16 30 29 25 17 28 14 ? 19 6 8 10 3 21 11 19 2 24 13 22 4 9 27 18 23 25 17 28 ? 36 6 8 10 3 21 11 19 2 24 13 22 4 9 27 18 6 8 10 3 21 11 19 2 24 13 22 4 9 27 18 23 25 17 28 29 14
result:
wrong output format Unexpected end of file - int32 expected
Subtask #3:
score: 0
Wrong Answer
Test #54:
score: 0
Wrong Answer
time: 4ms
memory: 4000kb
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:
wrong output format Unexpected end of file - int32 expected