QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#401831	#7418. Interactive Vertex	james1BadCreeper^#	TL	2ms	8268kb	C++14	1.6kb	2024-04-29 15:22:28	2024-04-29 15:22:29

Judging History

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

[2024-04-29 15:22:29]
评测

测评结果：TL
用时：2ms
内存：8268kb

查看

[2024-04-29 15:22:28]
提交

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.size()) 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) L = mid + 1; 
        else R = mid; 
    }
    int y = vec[L]; 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;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 8268kb

input:

output:

? 4 1 2 3 4 5 
! 1

result:

ok 1 queries

Test #2:

score: -100

Time Limit Exceeded

input:

output:

? 4 1 2 3 4 5 
? 2 1 2 3 
? 1 1 2 
? 1 3 1 
? 4 1 2 3 4 5 
? 2 1 2 3 
? 1 1 2 
? 1 3 1 
? 4 1 2 3 4 5 
? 2 1 2 3 
? 1 1 2 
? 1 3 1 
? 4 1 2 3 4 5 
? 2 1 2 3 
? 1 1 2 
? 1 3 1 
? 4 1 2 3 4 5 
? 2 1 2 3 
? 1 1 2 
? 1 3 1 
? 4 1 2 3 4 5 
? 2 1 2 3 
? 1 1 2 
? 1 3 1 
? 4 1 2 3 4 5 
? 2 1 2 3 
? 1 1 2 
?...