QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#722116	#9570. Binary Tree	ucup-team4474^#	RE	1ms	4012kb	C++20	2.3kb	2024-11-07 17:54:04	2024-11-07 17:54:04

Judging History

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

[2024-11-07 17:54:04]
评测

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

查看

[2024-11-07 17:54:04]
提交

answer

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

bool Memory_begin;

bool Memory_end;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cerr << (&Memory_end - &Memory_begin) / 1048576.0 << "MB" << '\n';

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<vector<int>> adj(n + 1);
        for (int i = 1, x, y; i <= n; i++)
        {
            cin >> x >> y;
            if (x)
                adj[i].push_back(x), adj[x].push_back(i);
            if (y)
                adj[i].push_back(y), adj[y].push_back(i);
        }
        vector<int> vis(n + 1);

        int siz = n;
        while (siz > 1)
        {
            vector<int> dep(n + 1);
            auto dfs = [&](auto &dfs, int cur, int fa) -> void
            {
                dep[cur] = dep[fa] + 1;
                for (int i : adj[cur])
                {
                    if (vis[i] or i == fa)
                        continue;
                    dfs(dfs, i, cur);
                }
            };
            for (int i = 1; i <= n; i++)
            {
                if (vis[i])
                    continue;
                dfs(dfs, i, 0);
                int p1 = max_element(dep.begin(), dep.end()) - dep.begin();
                dfs(dfs, p1, 0);
                auto dep1 = dep;
                int p2 = max_element(dep.begin(), dep.end()) - dep.begin();
                dfs(dfs, p2, 0);
                auto dep2 = dep;
                cout << "? " << p1 << ' ' << p2 << endl;
                int tmp;
                cin >> tmp;
                for (int j = 1; j <= n; j++)
                {
                    if (vis[j])
                        continue;
                    if (tmp == 0 and dep1[j] >= dep2[j])
                        vis[j] = 1, siz--;
                    else if (tmp == 1 and dep1[j] != dep2[j])
                        vis[j] = 1, siz--;
                    else if (tmp == 2 and dep1[j] <= dep2[j])
                        vis[j] = 1, siz--;
                }
                break;
            }
        }

        for (int i = 1; i <= n; i++)
        {
            if (!vis[i])
            {
                cout << "! " << i << endl;
                break;
            }
        }
    }
}
/*
 */

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 4012kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output: