QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#742801	#9570. Binary Tree	lmx111	TL	1ms	5716kb	C++20	3.1kb	2024-11-13 17:21:04	2024-11-13 17:21:13

Judging History

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

[2024-11-13 17:21:13]
评测

测评结果：TL
用时：1ms
内存：5716kb

查看

[2024-11-13 17:21:04]
提交

answer

#include <bits/stdc++.h>
#define int int64_t

// const char endl = '\n';
using std::endl;

const int maxn = (int)1.1E5;

int son[2][maxn], fa[maxn], sz[maxn], weight[maxn];

int num_now;
int center;

void dfs(int u) {
  sz[u] = 1;
  weight[u] = 0;
  for (int i = 0; i < 2; ++i) {
    if (son[i][u]) {
      dfs(son[i][u]);
      sz[u] += sz[son[i][u]];
      weight[u] = std::max(weight[u], sz[son[i][u]]);
    }
  }
  weight[u] = std::max(weight[u], num_now - sz[u]);
  if (center) return;
  if (weight[u] <= num_now / 2) center = u;
  // std::cout << "u: " << u << endl;
}

void solve() {
  int n;
  std::cin >> n;
  for (int i = 0; i <= n + 5; ++i) son[0][i] = son[1][i] = fa[i] = 0;
  for (int i = 1, x, y; i <= n; ++i) {
    std::cin >> x >> y;
    fa[son[0][i] = x] = fa[son[1][i] = y] = i;
  }
  int root = 0;
  for (int i = 1; i <= n; ++i)
    if (fa[i] == 0) root = i;
  int q = log2(n);
  int t;
  num_now = n;
  for (int j = 1; j <= q; ++j) {
    if (num_now == 1) {
      std::cout << "! " << root << endl;
      return;
    }
    center = 0;
    dfs(root);
    // std::cout << "center: " << center << endl;
    if (num_now == 2) {
      std::cout << "? " << center << ' ' << root << endl;
      std::cin >> t;
      if (t)
        std::cout << "! " << root << endl;
      else
        std::cout << "! " << center << endl;
      return;
    }
    int f = fa[center], ls = son[0][center], rs = son[1][center];
    int sz1 = num_now - sz[center];
    int minsz = std::min(sz1, std::min(sz[ls], sz[rs]));
    if (minsz == sz1) {
      std::cout << "? " << ls << ' ' << rs << endl;
      std::cin >> t;
      if (t == 0) {
        root = ls;
        num_now = sz[ls];
      }
      if (t == 2) {
        root = rs;
        num_now = sz[rs];
      }
      if (t == 1) {
        son[0][center] = son[1][center] = 0;
        num_now -= sz[ls] + sz[rs];
      }
    } else if (minsz == sz[ls]) {
      std::cout << "? " << f << ' ' << rs << endl;
      std::cin >> t;
      if (t == 0) {
        num_now -= sz[center];
        if (son[0][f] == center)
          son[0][f] = 0;
        else
          son[1][f] = 0;
      }
      if (t == 1) {
        root = center;
        num_now = sz[center] - sz[rs];
        son[1][center] = 0;
      }
      if (t == 2) {
        root = rs;
        num_now = sz[rs];
      }
    } else if (minsz == sz[rs]) {
      std::cout << "? " << f << ' ' << ls << endl;
      std::cin >> t;
      if (t == 0) {
        num_now -= sz[center];
        if (son[0][f] == center)
          son[0][f] = 0;
        else
          son[1][f] = 0;
      }
      if (t == 1) {
        root = center;
        num_now = sz[center] - sz[ls];
        son[0][center] = 0;
      }
      if (t == 2) {
        root = ls;
        num_now = sz[ls];
      }
    }
  }
}
int32_t main() {
#ifndef _DEBUG
  // std::ios::sync_with_stdio(false);
  // std::cin.tie(nullptr);
#endif
  int tc = 1;
  std::cin >> tc;
  while (tc--) solve();
#ifdef _DEBUG
  std::cout << std::endl;
  std::cout << "Time used: " << clock() << "ms" << std::endl;
  system("pause");
  return 0;
#endif
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 5716kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Time Limit Exceeded

input:

output: