QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#401846#7418. Interactive Vertexjames1BadCreeper#TL 3ms10152kbC++141.6kb2024-04-29 15:35:492024-04-29 15:35:50

Judging History

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

  • [2024-04-29 15:35:50]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:10152kb
  • [2024-04-29 15:35:49]
  • 提交

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]; }); 
    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) R = mid; 
        else L = mid + 1; 
        // cerr << L << " " << R << "\n"; 
    }
    int y = vec[R]; 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: 3ms
memory: 9520kb

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: 3ms
memory: 10152kb

input:

5
1 2
1 3
1 4
1 5

0
0
1
1

output:

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

result:

ok 4 queries

Test #3:

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

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: -100
Time Limit Exceeded

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 75 87 35 93 63 21 19 43 51 95 58 91 76 
? 7 ...

result: