QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#778623	#9570. Binary Tree	Clarus	RE	1ms	3536kb	C++20	3.5kb	2024-11-24 15:31:56	2024-11-24 15:31:57

Judging History

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

[2024-11-24 15:31:57]
评测

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

查看

[2024-11-24 15:31:56]
提交

answer

#include <bits/stdc++.h>

using LL = long long;

constexpr int inf = 1E9;

int ask(int a, int b)
{
    std::cout << "? " << a + 1 << ' ' << b + 1 << std::endl;
    int x;
    std::cin >> x;
    return x;    
}
void put(int x)
{
    std::cout << "! " << x + 1 << std::endl;
}

void solve()
{
    int n;
    std::cin >> n;

    std::vector<std::vector<int>> adj(n);
    std::vector<int> g;
    for (int i = 0; i < n; i++)
    {
        int v1, v2;
        std::cin >> v1 >> v2;
        v1--, v2--;
        if (v1 >= 0)
        {
            adj[i].emplace_back(g.size());
            g.emplace_back(v1);
            adj[v1].emplace_back(g.size());
            g.emplace_back(i);
        }
        if (v2 >= 0)
        {
            adj[i].emplace_back(g.size());
            g.emplace_back(v2);
            adj[v2].emplace_back(g.size());
            g.emplace_back(i);
        }
    }

    std::vector<int> vis(g.size());

    auto mark = [&](int x) -> void
    {
        vis[x] = true;
        vis[x ^ 1] = true;
    };

    std::vector<int> size(n);
    int cent = -1, root = 0;
    int m = -1;

    auto dfs1 = [&](auto &&self, int x, int fx) -> int
    {
        size[x] = 1;
        for (auto i : adj[x])
        {
            int y = g[i];
            if (vis[i] || y == fx)
            {
                continue;
            }
            size[x] += self(self, y, x);
        }
        return size[x];
    };
    auto dfs2 = [&](auto &&self, int x, int fx) -> void
    {
        int val = 0;
        for (auto i : adj[x])
        {
            int y = g[i];
            if (vis[i] || y == fx)
            {
                continue;
            }
            self(self, y, x);
            val = std::max(val, size[y]);
        }
        val = std::max(val, m - size[x]);
        if (val <= m / 2)
        {
            cent = x;
        }
    };
    auto work = [&](int root) -> void
    {
        m = dfs1(dfs1, root, -1);
        dfs2(dfs2, root, -1);
    };

    while (true)
    {
        work(root);
        std::cerr << "m = " << m << std::endl;
        if (m == 1)
        {
            put(root);
            break;
        }

        std::vector<std::array<int, 2>> e;
        for (auto i : adj[cent])
        {
            int y = g[i];
            if (vis[i])
            {
                continue;
            }
            e.push_back({y, i});
        }
        assert(e.size() > 0);
        if (e.size() == 1)
        {
            int q = ask(cent, e[0][0]);
            assert(q != 1);
            if (q == 0)
            {
                root = cent;
                mark(e[0][1]);
            }
            else
            {
                root = e[0][0];
                mark(e[0][1]);
            }
        }
        else
        {
            int q = ask(e[0][0], e[1][0]);
            if (q == 0)
            {
                root = e[0][0];
                mark(e[0][1]);
            }
            else if (q == 2)
            {
                root = e[1][0];
                mark(e[1][1]);
            }
            else
            {
                root = cent;
                mark(e[0][1]);
                mark(e[1][1]);
            }
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T;
    std::cin >> T;

    while (T--)
    {
        solve();
    }

    return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3536kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output: