QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#736034#9570. Binary TreenanometerRE 1ms3760kbC++176.5kb2024-11-11 23:42:472024-11-11 23:42:47

Judging History

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

  • [2024-11-11 23:42:47]
  • 评测
  • 测评结果：RE
  • 用时：1ms
  • 内存：3760kb
查看
  • [2024-11-11 23:42:47]
  • 提交

answer

#include <bits/stdc++.h>
// #define endl '\n'
#define int long long
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int query(int u, int v)
{
    fflush(stdout);
    cout << "? " << u << " " << v << endl;
    int x;
    cin >> x;
    return x;
}
void solve()
{
    int n;
    cin >> n;
    vector<set<int>> e(n + 1);
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        if (x != 0)
        {
            e[i].insert(x);
            e[x].insert(i);
        }
        if (y != 0)
        {
            e[i].insert(y);
            e[y].insert(i);
        }
    }
    int duan1 = 1;

    auto find_mid = [&](int p) -> int
        {
            int minl = 1e18;
            int ans = p;
            int ans_p = p;
            vector<int> sz(n + 1, 0);
            vector<int> dp(n + 1, 0);
            int cnt = 0;
            vector<int> donee(n + 1, 0);
            auto dfs2 = [&](auto dfs2, int u) -> void
                {
                    cnt++;
                    for (auto pp : e[u])
                    {
                        if (donee[pp] == 1)
                            continue;
                        donee[pp] = 1;
                        dfs2(dfs2, pp);
                    }
                };
            donee[p] = 1;
            dfs2(dfs2, p);

            auto dfs = [&](auto dfs, int u, int fa) -> int
                {
                    vector<int> t;
                    int sum = 0;
                    for (auto pp : e[u]) // 链式前向星遍历
                    {
                        if (pp == fa)continue;
                        int now = dfs(dfs, pp, u);
                        t.push_back(now + 1);
                        t.push_back(n - now);
                        sum += now;
                    }
                    t.push_back(cnt - sum);
                    t.push_back(sum + 1);
                    //cout << u << "------------------\n";
                    for (auto x : t)
                    {
                        if (x == (cnt - 1) / 2 + 1) ans = u;
                    }
                    //cout << endl;

                    return sum + 1;
                };
            dfs(dfs, p, 0);
            return ans;
        };

    // cerr << find_mid(1) << endl;

    auto cont_size = [&](int p, int x) -> int
        {
            queue<int> qq;
            qq.push(p);
            vector<int> done(n + 1, 0);
            done[x] = 1;
            while (!qq.empty())
            {
                int pp = qq.front();
                qq.pop();
                done[pp] = 1;
                for (auto nxt : e[pp])
                {
                    if (done[nxt] == 0)
                        qq.push(nxt);
                }
            }

            int cnt = 0;
            for (int i = 1; i <= n; i++)
            {
                cnt += done[i];
            }
            return cnt;
        };

    while (1)
    {
        int p_mid = find_mid(duan1);
        // cerr << "________________" << endl;
        // for (auto ppp : e[2])
        //{
        //     cout << ppp << " ";
        // }
        // cerr << endl<<endl;
        //cerr << "_____  " << p_mid << " " << duan1 << endl;
        if (e[p_mid].size() == 0)
        {
            cout << "! " << p_mid << endl;
            return;
        }
        else if (e[p_mid].size() == 1)
        {
            vector<int> lin;
            for (auto p : e[p_mid])
            {
                lin.push_back(p);
            }
            if (query(p_mid, lin[0]) == 0)
                cout << "! " << p_mid << endl;
            else
                cout << "! " << lin[0] << endl;
            return;
        }
        else if (e[p_mid].size() == 2)
        {
            vector<int> lin;
            for (auto p : e[p_mid])
            {
                lin.push_back(p);
            }

            int op = query(lin[0], lin[1]);
            if (op == 0)
            {
                e[p_mid].erase(lin[0]);
                e[lin[0]].erase(p_mid);
                duan1 = lin[0];
            }
            else if (op == 1)
            {
                cout << "! " << p_mid << endl;
                return;
            }
            else if (op == 2)
            {
                e[p_mid].erase(lin[1]);
                e[lin[1]].erase(p_mid);
                duan1 = lin[1];
            }
        }
        else if (e[p_mid].size() == 3)
        {
            vector<int> lin;
            for (auto p : e[p_mid])
            {
                lin.push_back(p);
            }

            vector<int> cnt_lin(3);
            for (int i = 0; i < 3; i++)
            {
                cnt_lin[i] = cont_size(lin[i], p_mid);
            }

            int mmin = cnt_lin[0];
            int p_mmin = 0;
            for (int i = 0; i < 3; i++)
            {
                if (cnt_lin[i] < mmin)
                {
                    mmin = cnt_lin[i];
                    p_mmin = i;
                }
            }

            int a, b;
            if (p_mmin == 0)
            {
                a = lin[1];
                b = lin[2];
            }
            else if (p_mmin == 1)
            {
                a = lin[0];
                b = lin[2];
            }
            else if (p_mmin == 2)
            {
                a = lin[1];
                b = lin[0];
            }

            int op = query(a, b);
            if (op == 0)
            {
                e[p_mid].erase(a);
                e[a].erase(p_mid);
                duan1 = a;
            }
            else if (op == 1)
            {
                e[p_mid].erase(a);
                e[a].erase(p_mid);
                e[p_mid].erase(b);
                e[b].erase(p_mid);
                duan1 = p_mid;
            }
            else if (op == 2)
            {
                e[p_mid].erase(b);
                e[b].erase(p_mid);
                duan1 = b;
            }
        }
    }
    // for (int i=1;i<=n;i++)
    // {
    //     cerr<<i<<" "<<e[i].size()<<endl;
    // }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

/*


8
2 0
8 6
0 0
3 0
0 0
7 0
0 0
5 4






8
0 0
1 4
2 0
0 0
7 8
0 0
3 0
6 0



8
5 8
0 0
1 7
0 0
0 0
4 2
0 0
6 0


*/
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3760kb

input:

2
5
0 0
1 5
2 4
0 0
0 0
1
0
2
0 2
0 0
2

output:

? 3 5
? 2 1
! 2
? 1 2
! 2

result:

ok OK (2 test cases)

Test #2:

score: -100
Runtime Error

input:

5555
8
2 0
8 6
0 0
3 0
0 0
7 0
0 0
5 4
2
0
0
8
0 0
1 4
2 0
0 0
7 8
0 0
3 0
6 0
2
2
0
8
5 8
0 0
1 7
0 0
0 0
4 2
0 0
6 0
2
1
0
5
4 5
3 1
0 0
0 0
0 0
0
0
8
0 0
0 0
5 6
0 0
1 4
2 0
3 8
0 0
0
1
5
3 0
5 1
0 0
0 0
4 0
0
2
5
5 0
0 0
0 0
3 0
2 4
2
0
3
3 0
1 0
0 0
2
2
2 0
0 0
2
3
2 3
0 0
0 0
1
10
2 8
9 7
0 0
...

output:

? 6 8
? 4 5
? 4 3
! 4
? 2 7
? 7 8
? 8 6
! 8
? 3 8
? 4 8
? 6 2
! 6
? 2 5
? 2 3
! 2
? 5 7
? 1 4
! 5
? 1 5
? 1 3
! 3
? 2 4
? 4 3
! 4
? 2 3
! 3
? 1 2
! 2
? 2 3
! 1
? 7 9
? 4 7
? 6 3
! 6
? 1 2
! 2
? 5 9
? 5 8
? 3 4
! 3
? 3 10
? 6 8
? 8 10
! 10
? 3 9
? 7 9
? 2 1
! 1
? 1 2
! 2
? 4 3
? 1 7
! 7
? 4 9
? 4 8
?...

result:
English 繁體中文 简体中文

Server Time: 2025-01-22 09:20:28 | OpenSource Project