QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#401851#7418. Interactive Vertexjames1BadCreeper#WA 3ms10116kbC++141.7kb2024-04-29 15:44:042024-04-29 15:44:04

Judging History

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

  • [2024-04-29 15:44:04]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:10116kb
  • [2024-04-29 15:44:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5; 

int n, ans = -1; 
vector<int> G[N]; 
bool vis[N]; 
int sz[N], mxs[N], rt; 

int ask(int x, vector<int> v) {
    cout << "? " << v.size() << ' ' << x << ' '; 
    for (int i : v) cout << i << ' '; 
    cout << endl; cin >> x; 
    return x; 
}

void froot(int x, int fa, int tot) {
    sz[x] = 1; mxs[x] = 0; 
    for (int y : G[x]) if (y != fa && !vis[y])
        froot(y, x, tot), sz[x] += sz[y], mxs[x] = max(mxs[x], sz[y]); 
    mxs[x] = max(mxs[x], tot - sz[x]); 
    if (mxs[rt] > mxs[x]) rt = x; 
}

void solve(int x) {
    if (ans != -1) return; 
    vector<int> vec; 
    for (int y : G[x]) if (!vis[y]) vec.emplace_back(y); 
    if (vec.empty()) return ans = x, void(); 
    if (ask(x, vec) == 1) return ans = x, void(); 
    // sort(vec.begin(), vec.end(), [&](int u, int v){ return sz[u] < sz[v]; }); 
    vis[x] = 1; 
    int L = 0, R = vec.size() - 1; 
    while (L < R) {
        int mid = L + R >> 1; // 3 4
        vector<int> now; 
        for (int i = L; i <= mid; ++i) now.emplace_back(vec[i]); 
        if (ask(x, now) == 1) L = mid + 1; 
        else R = mid; 
        // cerr << L << " " << R << endl; 
    }
    int y = vec[L]; 
    // cerr << "FOUND " << y << endl; 
    int all = sz[y];  
    rt = 0; froot(y, 0, all); froot(rt, 0, all); 
    solve(rt); 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n; 
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v; 
        G[u].emplace_back(v); G[v].emplace_back(u); 
    }
    mxs[0] = 1e9; 
    int all = n; 
    froot(1, 0, all); froot(rt, 0, all); 
    solve(rt); 
    cout << "! " << ans << endl; 
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 10116kb

input:

5
1 2
1 3
1 4
1 5

1

output:

? 4 1 2 3 4 5 
! 1

result:

ok 1 queries

Test #2:

score: 0
Accepted
time: 0ms
memory: 8312kb

input:

5
1 2
1 3
1 4
1 5

0
0
0

output:

? 4 1 2 3 4 5 
? 2 1 2 3 
? 1 1 2 
! 2

result:

ok 3 queries

Test #3:

score: 0
Accepted
time: 0ms
memory: 8536kb

input:

7
1 2
2 3
3 4
4 5
3 6
6 7

1

output:

? 3 3 2 4 6 
! 3

result:

ok 1 queries

Test #4:

score: 0
Accepted
time: 2ms
memory: 8236kb

input:

100
75 98
98 87
35 98
98 93
98 63
83 25
98 21
97 25
19 98
8 25
43 98
28 94
92 28
51 98
6 28
95 98
58 98
12 28
4 42
9 28
30 25
91 98
28 77
98 76
24 42
28 82
14 25
28 32
98 1
81 98
42 50
98 71
98 26
20 98
80 39
28 23
70 28
88 25
69 28
28 99
41 98
98 55
29 98
61 28
27 28
11 25
98 84
34 28
98 100
36 98
...

output:

? 51 98 75 87 35 93 63 21 19 43 51 95 58 91 76 1 81 71 26 20 41 55 29 84 100 36 79 15 85 56 45 48 52 62 28 78 46 96 64 59 18 2 89 68 90 65 31 66 13 54 17 40 73 
? 26 98 75 87 35 93 63 21 19 43 51 95 58 91 76 1 81 71 26 20 41 55 29 84 100 36 79 15 
? 13 98 85 56 45 48 52 62 28 78 46 96 64 59 18 
? 7 ...

result:

ok 22 queries

Test #5:

score: 0
Accepted
time: 3ms
memory: 9304kb

input:

203
139 160
172 95
170 39
106 39
3 95
6 39
130 16
148 65
62 160
109 39
39 69
23 16
95 84
39 11
95 37
36 39
95 103
60 39
94 39
39 35
39 123
138 39
199 39
5 16
65 160
142 16
77 39
135 39
97 39
39 72
95 92
39 44
65 200
65 129
39 152
39 176
16 86
16 95
39 143
198 39
95 90
39 17
197 39
89 16
95 189
16 47...

output:

? 102 39 170 106 6 109 69 11 36 60 94 35 123 138 199 77 135 97 72 44 152 176 143 198 17 197 178 127 78 102 180 157 191 38 91 192 114 185 25 122 113 28 24 131 64 147 54 46 184 43 95 57 196 169 79 161 175 203 51 12 154 136 73 190 158 121 179 159 10 19 112 58 171 59 120 63 98 88 66 68 188 145 124 83 12...

result:

ok 30 queries

Test #6:

score: -100
Wrong Answer
time: 3ms
memory: 8436kb

input:

406
77 136
231 136
177 130
390 136
342 127
136 128
254 136
136 32
136 295
102 342
137 214
342 3
120 136
43 406
406 55
72 371
136 183
136 97
331 72
342 397
108 136
136 315
136 105
72 316
136 328
136 111
214 327
335 130
136 203
72 110
406 355
136 336
107 136
136 333
136 330
339 136
84 406
136 152
201 ...

output:

? 204 136 77 231 390 128 254 32 295 120 183 97 108 315 105 328 111 203 336 107 333 330 339 152 217 306 236 116 370 26 133 129 95 22 374 318 352 1 302 237 279 233 69 202 76 88 141 200 191 194 266 234 263 299 239 192 157 53 325 240 262 44 362 210 391 280 142 50 367 75 358 90 40 395 228 180 301 184 265...

result:

wrong answer too many queries: 37 queries, bigger than 36