QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#728651	#9570. Binary Tree	ucup-team112^#	RE	0ms	3604kb	C++20	5.6kb	2024-11-09 15:35:17	2024-11-09 15:35:19

Judging History

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

[2024-11-09 15:35:19]
评测

测评结果：RE
用时：0ms
内存：3604kb

查看

[2024-11-09 15:35:17]
提交

answer

#include <bits/stdc++.h>
#include <bitset>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <random>
#include <set>
#include <type_traits>
#include <unordered_map>

using namespace std;
using ll = long long;

#define rep(i, n, m) for (ll(i) = (n); (i) < (m); (i)++)
#define rrep(i, n, m) for (ll(i) = (n); (i) > (m); (i)--)
const ll mod = 998244353;
const ll inf = 1e18;
const ll INF = 4e18 + 10;

using pll = pair<ll, ll>;

void pline(vector<int> lis) {
    rep(i, 0, lis.size()) {
        printf("%d", lis[i]);
        if (i != lis.size() - 1)
            printf(" ");
        else
            printf("\n");
    }
}

void pline(vector<ll> lis) {
    rep(i, 0, lis.size()) {
        printf("%lld", lis[i]);
        if (i != lis.size() - 1)
            printf(" ");
        else
            printf("\n");
    }
}

void pline2(vector<ll> lis) {
    rep(i, 0, lis.size()) {
        printf("%lld", lis[i]);
        if (i != lis.size() - 1)
            printf("");
        else
            printf("\n");
    }
}

void pline(vector<pair<ll, ll>> lis) {
    rep(i, 0, lis.size()) {
        printf("/%lld,%lld/", lis[i].first, lis[i].second);
        if (i != lis.size() - 1)
            printf(" ");
        else
            printf("\n");
    }
}

// 全方位1回目
void dfsA(ll v, ll p, vector<vector<ll>> &lis, vector<bool> &able, vector<ll> &csize) {
    csize[v] = 1;
    for (ll nex : lis[v]) {
        if (able[nex] && (nex != p)) {
            dfsA(nex, v, lis, able, csize);
            csize[v] += csize[nex];
        }
    }
}

// 全方位2回目
void dfsB(ll v, ll p, vector<vector<ll>> &lis, vector<bool> &able, vector<ll> &csize,
          vector<ll> &ablevs, vector<ll> &centorid) {

    ll cssum = 0;
    vector<ll> cslis;

    for (ll nex : lis[v]) {
        if (able[nex] && (nex != p)) {
            dfsB(nex, v, lis, able, csize, ablevs, centorid);
            cslis.push_back(csize[nex]);
            cssum += csize[nex];
        }
    }

    cslis.push_back(ablevs.size() - 1 - cssum);

    ll csmax = 0;
    for (ll tmp : cslis) {
        csmax = max(csmax, tmp);
    }

    if (csmax <= ablevs.size() / 2) {
        centorid.push_back(v);
    }
}

// 消去
void dfsC(ll v, ll p, vector<vector<ll>> &lis, vector<bool> &able) {
    for (ll nex : lis[v]) {
        if (able[nex] && (nex != p)) {
            dfsC(nex, v, lis, able);
        }
        able[v] = false;
    }
}

void dfsD(ll v, ll p, vector<vector<ll>> &lis, vector<bool> &able) {
    for (ll nex : lis[v]) {
        if (able[nex] && (nex != p)) {
            dfsC(nex, v, lis, able);
        }
        able[v] = false;
    }
}

int main() {

    ll TT;
    cin >> TT;

    rep(loop, 0, TT) {

        ll n;
        cin >> n;
        vector<vector<ll>> lis(n);

        rep(i, 0, n) {
            ll x, y;
            cin >> x >> y;
            x--;
            y--;

            if (x != -1) {
                lis[i].push_back(x);
                lis[x].push_back(i);
            }
            if (y != -1) {
                lis[i].push_back(y);
                lis[y].push_back(i);
            }
        }

        // 可能性がある頂点
        vector<bool> able(n, true);

        while (1) {

            // ありうる頂点
            vector<ll> ablevs(0);
            rep(v, 0, n) {
                if (able[v]) {
                    ablevs.push_back(v);
                }
            }

            if (ablevs.size() == 1) {
                cout << "! " << ablevs[0] + 1 << flush << endl;
                break;
            }

            // 重心を求める
            vector<ll> csize(n, 0);
            vector<ll> centorid(0);

            dfsA(ablevs[0], -1, lis, able, csize);
            dfsB(ablevs[0], -1, lis, able, csize, ablevs, centorid);

            if (centorid.size() == 2) {
                cout << "? " << centorid[0] + 1 << " " << centorid[1] + 1 << flush << endl;
                ll cat;
                cin >> cat;

                if (cat == 0) {
                    dfsC(centorid[1], centorid[0], lis, able);
                } else {
                    dfsC(centorid[0], centorid[1], lis, able);
                }
            } else if (centorid.size() == 1) {

                vector<pll> cvs;
                for (ll nex : lis[centorid[0]]) {
                    if (able[nex]) {
                        ll sss = min(csize[nex], (ll)ablevs.size() - csize[nex]);
                        cvs.push_back(make_pair(sss, nex));
                    }
                }

                sort(cvs.begin(), cvs.end());
                reverse(cvs.begin(), cvs.end());

                cout << "? " << cvs[0].second + 1 << " " << cvs[1].second + 1 << flush << endl;
                ll cat;
                cin >> cat;

                if (cat == 0) {
                    dfsC(cvs[1].second, centorid[0], lis, able);
                    if (cvs.size() >= 3) {
                        dfsC(cvs[2].second, centorid[0], lis, able);
                    }
                    able[centorid[0]] = false;
                } else if (cat == 2) {
                    dfsC(cvs[0].second, centorid[0], lis, able);
                    if (cvs.size() >= 3) {
                        dfsC(cvs[2].second, centorid[0], lis, able);
                    }
                    able[centorid[0]] = false;
                } else {
                    dfsC(cvs[1].second, centorid[0], lis, able);
                    dfsC(cvs[0].second, centorid[0], lis, able);
                }
            }
        }
    }
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3604kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output: