QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#733665	#9570. Binary Tree	ucup-team5799	RE	1ms	3448kb	C++20	3.6kb	2024-11-10 20:23:36	2024-11-10 20:23:37

Judging History

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

[2024-11-10 20:23:37]
评测

测评结果：RE
用时：1ms
内存：3448kb

查看

[2024-11-10 20:23:36]
提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using LL = long long;

void RES(int x) {
    cout << "! " << x << endl;
}

void ASK(int u, int v) {
    cout << "? " << u << " " << v << endl;
}

int GET() {
    int op; cin >> op;
    return op;
}

void solve() {
    int n; cin >> n;
    vector<vector<int>> G(n + 1);
    for (int i = 1;i <= n;i++) {
        int a, b; cin >> a >> b;
        if (a) {
            G[a].push_back(i);
            G[i].push_back(a);
        }
        if (b) {
            G[b].push_back(i);
            G[i].push_back(b);
        }
    }

    auto removeit = [&](vector<int>& arr, int x) {
        int pos = -1;
        for (int i = 0;i < arr.size();i++) {
            if (arr[i] == x) {
                pos = i;
                break;
            }
        }
        if (pos != -1) {
            arr.erase(arr.begin() + pos);
        }
    };

    auto dfs = [&](auto&&dfs, int st, int ps) -> void {
        int m = 0;
        auto cnt = [&](auto&&cnt, int u, int fa) -> void {
            m++;
            for (int v : G[u]) {
                if (v == fa) continue;
                cnt(cnt, v, u);
            }
        };
        cnt(cnt, st, ps);

        // cout << "m: " << m << endl;

        vector<int> sz(n + 1, 0), w(n + 1, 0), centroid(2, 0);
        auto getCentroid = [&](auto&&getCentroid, int u, int fa) -> void {
            sz[u] = 1;
            w[u] = 0;
            for (int v : G[u]) {
                if (v == fa) continue;
                getCentroid(getCentroid, v, u);
                sz[u] += sz[v];
                w[u] = max(w[u], sz[v]);
            }
            w[u] = max(w[u], m - sz[u]);
            // cout << u << ": " << w[u] << endl;
            if (w[u] <= m / 2) centroid[centroid[0] != 0] = u;
        };
        getCentroid(getCentroid, st, ps);
        int root = centroid[0];
        if (G[root].size() == 1 && centroid[1] != 0) {
            root = centroid[1];
        }

        // cout << "root: " << root << " " << G[root].size() << endl;
        auto& son = G[root];
        if (son.size() == 0) {
            RES(root);
            return;
        }
        else if (son.size() == 1) {
            ASK(root, son[0]);
            int op = GET();
            if (op == 0) RES(root);
            else RES(son[0]);
            return;
        }
        else if (son.size() == 2) {
            int lson = son[0], rson = son[1];
            removeit(G[lson], root);
            removeit(G[rson], root);
            // remove(G[lson].begin(), G[lson].end(), root);
            // remove(G[rson].begin(), G[rson].end(), root);
            G[root].clear();
            ASK(lson, rson);
            int op = GET();
            if (op == 1) {
                RES(root);
                return;
            }
            else if (op == 0) dfs(dfs, lson, root);
            else dfs(dfs, rson, root);
        }
        else if (son.size() == 3) {
            int lson = son[0], rson = son[1], tson = son[2];
            removeit(G[lson], root);
            removeit(G[rson], root);
            // remove(G[lson].begin(), G[lson].end(), root);
            // remove(G[rson].begin(), G[rson].end(), root);
            G[root].clear();
            G[root].push_back(tson);
            ASK(lson, rson);
            int op = GET();
            if (op == 1) {
                dfs(dfs, root, root);
            }
            else if (op == 0) dfs(dfs, lson, root);
            else dfs(dfs, rson, root);
        }
    };
    dfs(dfs, 1, 1);
}

int main() {
    int t; cin >> t;
    while(t--) solve();
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3448kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output: