QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#396676#4926. Where Is the Root?hos_lyric7 4ms4136kbC++143.6kb2024-04-23 00:40:402024-04-23 00:40:40

Judging History

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

  • [2024-04-23 00:40:40]
  • 评测
  • 测评结果:7
  • 用时:4ms
  • 内存:4136kb
  • [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