QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#751109	#9570. Binary Tree	ucup-team5799	RE	1ms	3564kb	C++14	3.6kb	2024-11-15 17:07:42	2024-11-15 17:07:44

Judging History

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

[2024-11-15 17:07:44]
评测

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

查看

[2024-11-15 17:07:42]
提交

answer

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

struct node{
    int to;
    int id;
};

void solve(){
    int n;
    cin >> n;
    vector<vector<node>> e(n + 1);
    int times = 0;
    vector<int> vi(n * 5);
    for(int i = 1; i <= n; i++){
        int a, b;
        cin >> a >> b;
        if(a != 0){
            e[a].push_back({i, ++times});
            e[i].push_back({a, times});
            vi[times] = 1;
        }
        if(b != 0){
            e[i].push_back({b, ++times});
            e[b].push_back({i, times});
            vi[times] = 1;
        }
    }

    auto find = [&](int x) -> int {
        vector<int> fa(n + 1);
        vector<int> ans(n + 1);
        vector<int> siz(n + 1);
        vector<int> big(n + 1);
        auto dfs = [&](auto&& dfs, int u) -> void {
            // cout << u << endl;
            siz[u] = 1;
            ans[u] = u;
            for(auto [v, id] : e[u]){
                if(vi[id] == 0)continue;
                if(fa[u] == v){continue;}
                fa[v] = u;
                dfs(dfs, v);
                siz[u] += siz[v];
                big[u] = max(big[u], siz[v]);
            }
            for(auto [v, id] : e[u]){
                if(vi[id] == 0)continue;
                if(fa[u] == v){continue;}
                int p = ans[v];
                while(p != u){
                    if(max(big[p], siz[u] - siz[p]) <= siz[u] / 2){
                        ans[u] = p;
                        break;
                    }else{
                        p = fa[p];
                    }
                }
            }
        };
        fa[x] = x;
        dfs(dfs, x);
        return ans[x];
    };
    bool ok = 0;
    auto work = [&](auto&& work, int u) -> void {
        if(ok)return ;
        // cout << "aaaaa" << endl;
        u = find(u);
        int cnt = 0;
        vector<node> temp;
        for(auto [v, id] : e[u]){
            if(vi[id]){cnt++; temp.push_back({v, id});}
        }
        if(cnt == 0){cout << "! " << u << endl;}
        else if(cnt == 1){
            int f = temp[0].to;
            cout << "? " << f << " " << u << endl;
            int op;
            cin >> op;
            if(op == 0){cout << "! " << f << endl;return ;}
            else if(op == 2){cout << "! " << u << endl; return ;}
        }
        else if(cnt == 2){
            int f = temp[0].to;
            int v = temp[1].to;
            cout << "? " << f << " " << v << endl;
            int op;
            cin >> op;
            if(op == 1){
                cout << "! " << u << endl;
                return ;
            }
            else if(op == 0){
                vi[temp[0].id] = 0;
                work(work, f);
            }
            else if(op == 2){
                vi[temp[1].id] = 0;
                work(work, v);
            }
        }
        else if(cnt == 3){
            int f = temp[0].to;
            int v = temp[1].to;
            cout << "? " << f << " " << v << endl;
            int op;
            cin >> op;
            if(op == 1){
                vi[temp[0].id] = 0;
                vi[temp[1].id] = 0;
                work(work, u);
            }
            else if(op == 0){
                vi[temp[0].id] = 0;
                work(work, f);
            }
            else if(op == 2){
                vi[temp[1].id] = 0;
                work(work, v);
            }
        }
    };
    work(work, 1);


}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    solve();
    return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3564kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output: