QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#795950	#9570. Binary Tree	nhuang685	RE	1ms	3848kb	C++23	2.9kb	2024-12-01 05:00:41	2024-12-01 05:00:45

Judging History

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

[2024-12-01 05:00:45]
评测

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

查看

[2024-12-01 05:00:41]
提交

answer

/**
 * @author n685
 * @brief
 * @date 2024-11-30 15:19:48
 *
 *
 */
#include "bits/stdc++.h"

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif

namespace rs = std::ranges;
namespace rv = std::views;

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

int query(int u, int v) {
  std::cout << "? " << u + 1 << ' ' << v + 1 << std::endl;
  int t;
  std::cin >> t;
  return t;
}

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

  std::vector<std::vector<int>> adj(n);
  for (int i = 0; i < n; ++i) {
    int x, y;
    std::cin >> x >> y;
    --x;
    --y;
    if (x != -1) {
      adj[i].push_back(x);
      adj[x].push_back(i);
    }
    if (y != -1) {
      adj[i].push_back(y);
      adj[y].push_back(i);
    }
  }

  std::vector<int> sub(n);
  auto comp = [&](auto&& self, int node, int par) -> void {
    sub[node] = 1;
    for (int i : adj[node]) {
      if (i == par) {
        continue;
      }
      self(self, i, node);
      sub[node] += sub[i];
    }
  };
  auto cent = [&](auto&& self, int node, int par) -> int {
    for (int i : adj[node]) {
      if (i != par && 2 * sub[i] > sub[node]) {
        return self(self, i, node);
      }
    }
    return node;
  };
  comp(comp, 0, -1);
  int node = cent(cent, 0, -1);
  while (std::ssize(adj[node]) > 0) {
    comp(comp, node, -1);
    if (std::ssize(adj[node]) == 1) {
      int t = query(node, adj[node][0]);
      if (t == 2) {
        node = adj[node][0];
      }
      break;
    }
    if (std::ssize(adj[node]) == 2) {
      int u = adj[node][0], v = adj[node][1];
      int t = query(u, v);
      if (t == 1) {
        break;
      }
      if (t == 0) {
        std::erase(adj[u], node);
        node = u;
      } else {
        std::erase(adj[v], node);
        node = v;
      }
    } else {
      std::array<int, 3> ord{adj[node][0], adj[node][1], adj[node][2]};
      if (sub[ord[0]] < sub[ord[1]]) {
        std::swap(ord[0], ord[1]);
      }
      if (sub[ord[1]] < sub[ord[2]]) {
        std::swap(ord[1], ord[2]);
      }
      if (sub[ord[0]] < sub[ord[1]]) {
        std::swap(ord[0], ord[1]);
      }
      int t = query(ord[0], ord[1]);
      if (t == 0) {
        std::erase(adj[ord[0]], node);
        node = ord[0];
      } else if (t == 1) {
        std::erase(adj[node], ord[0]);
        std::erase(adj[node], ord[1]);
      } else {
        std::erase(adj[ord[1]], node);
        node = ord[1];
      }
    }
    comp(comp, node, -1);
    node = cent(cent, node, -1);
  }
  std::cout << "! " << node + 1 << std::endl;
}

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int t;
  std::cin >> t;
  for (int i = 0; i < t; ++i) {
    dbg(i + 1);
    solve();
    bar();
  }
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3848kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output: