QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#733104#9570. Binary Treeqinglu09#TL 2ms5704kbC++234.5kb2024-11-10 17:13:152024-11-10 17:13:17

Judging History

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

  • [2024-11-10 17:13:17]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:5704kb
  • [2024-11-10 17:13:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int>pii;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
// #define endl '\n'
#define debug(x) cout<<#x<<": "<<x<<endl
const int N=2e5+10;
typedef pair<ll,ll>PLL;

int n;
vector<int>ve[N];
int fa[N], siz[N], tot = 0, root;
pii e[N];
int degree[N];

void answer(int x)
{
    cout << "! " << x << endl;
    cout.flush();
}

int ask(int x, int y)
{
    cout << "? " << x << ' ' << y << endl;
    cout.flush();
    cin >> x;
    return x;
}

void init_dfs(int u, int f)
{
    siz[u]++;
    for(int v : ve[u])
    {
        if(f != v)
        {
            fa[v] = u;
            e[++tot] = {v, u};
            init_dfs(v, u);
            siz[u] += siz[v];
        }
    }
}

void dfs(int u, int f)
{
    siz[u]++;
    for(int v : ve[u])
    {
        if(f != v)
        {
            degree[u]++;
            degree[v]++;
            fa[v] = u;
            dfs(v, u);
            siz[u] += siz[v];
        }
    }
}

void cut(int u, int f, int c)
{
    siz[u]++;
    for(int v : ve[u])
    {
        if(f != v && c != v)
        {
            degree[u]++;
            degree[v]++;
            fa[v] = u;
            cut(v, u, c);
            siz[u] += siz[v];
        }
    }
}

void solve()
{
    cin >> n;
    rep(i, 1, n)
    {
        ve[i].clear();
        fa[i] = 0;
        siz[i] = 0;
        degree[i] = 0;
    }
    rep(i, 1, n)
    {
        int u, v;
        cin >> u >> v;
        if(u)
        {
            ve[u].push_back(i);
            ve[i].push_back(u);
            degree[i]++;
            degree[u]++;
        }
        if(v)
        {
            ve[v].push_back(i);
            ve[i].push_back(v);
            degree[v]++;
            degree[i]++;
        }
    }
    tot = 0;
    init_dfs(1, 0);
    root = 1;
    // cout << root << endl;
    // rep(i, 1, n) {
    //     cout << i << ": " << degree[i] << ' ' << siz[i] << ' ' << endl;
    // }
    while(1)
    {
        int s = 0;
        rep(i, 1, n)
        {
            if(degree[i]) s++;
        }
        if(!s)
        {
            answer(root);
            return;
        }
        int id1 = -1, id2 = -1, minn = 1e9;
        if(s == 3)
        {
            int ans = 0;
            rep(i, 1, n)
            {
                if(degree[i] == 1)
                {
                    if(id1 == -1)
                    {
                        id1 = i;
                    }
                    else
                    {
                        id2 = i;
                    }
                }
                if(degree[i] == 2)
                {
                    ans = i;
                }
            }
            int op = ask(id1, id2);
            if(op == 0)
            {
                answer(id1);
                return;
            }
            if(op == 1)
            {
                answer(ans);
                return;
            }
            if(op == 2)
            {
                answer(id2);
                return;
            }
        }
        rep(i, 1, tot)
        {
            auto [x, y] = e[i];
            if(!siz[x] || !siz[y]) continue;
            int down = siz[x], up = siz[root] - siz[x];
            if(down && up)
            {
                if(abs(down - up) < minn)
                {
                    minn = abs(down - up);
                    id1 = x;
                    id2 = y;
                }
            }
        }
        int op = ask(id1, id2);
        if(op == 0)
        {
            rep(i, 1, n)
            {
                degree[i] = 0;
                siz[i] = 0;
            }
            root = id1;
            dfs(root, fa[root]);
        }
        if(op == 2)
        {
            rep(i, 1, n)
            {
                degree[i] = 0;
                siz[i] = 0;
            }
            cut(root, fa[root], id1);
        }
        // cout << root << endl;
        // rep(i, 1, n) {
        //     cout << i << ": " << degree[i] << ' ' << siz[i] << ' ' << endl;
        // }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
// #ifndef  ONLINEJUDGE
//     freopen("test.in","r",stdin);
//     freopen("test.out","w",stdout);
// #endif
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5704kb

input:

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

output:

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

result:

ok OK (2 test cases)

Test #2:

score: -100
Time Limit Exceeded

input:

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

output:

? 8 2
? 6 2
? 7 6
! 6
? 7 3
? 8 5
? 5 7
? 5 6

result: