QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#813112#9866. Extracting Weightstest_algthWA 1ms3656kbC++172.2kb2024-12-13 22:02:342024-12-13 22:02:40

Judging History

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

  • [2024-12-13 22:02:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3656kb
  • [2024-12-13 22:02:34]
  • 提交

answer

#include <bits/stdc++.h>

const int MAXN = 255;
std::vector <int> adj[MAXN];
std::bitset <MAXN> lb[MAXN], now;
int W[MAXN], dep[MAXN], fa[MAXN], Ans[MAXN];
bool ok[MAXN];
std::array <int, 3> query[MAXN];
int N, K, cnts, top;

void solve(int u, int pa) {
  dep[u] = dep[pa] + 1, fa[u] = pa;
  for (int v : adj[u]) {
    if (dep[v]) continue;
    solve(v, u);
  }
}

inline int lca(int a, int b) {
  if (dep[a] < dep[b]) std::swap(a, b);
  now.set(a), now.set(b);
  while (dep[a] > dep[b]) a = fa[a], now.set(a);
  if (a == b) return a;
  while (a != b) a = fa[a], b = fa[b], now.set(a), now.set(b);
  return a;
}

inline int Insert() {
  for (int i = 1; i <= N; ++i) {
    if (ok[i]) {
      if (now[i]) now ^= lb[i];
    } else if (now[i]) {
      lb[i] = now, ++cnts, ok[i] = true;
      return i;
    }
  }
  return -1;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  std::cin >> N;
  lb[1].set(cnts = 1), ok[1] = true;
  for (int i = 1, u, v; i < N; ++i) {
    std::cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  solve(1, 0);
  for (int i = 1; i <= N && cnts < N; ++i) {
    for (int j = 1; j <= N && cnts < N; ++j) {
      if (i == j) continue;
      now.reset();
      int len = dep[i] + dep[j] - 2 * dep[lca(i, j)];
      if (len != K) continue;
      int res = Insert();
      if (res != -1) {
        query[++top] = {i, j, res};
      }
    }
  }

  std::cout << "YES\n";
  std::cout << "? " << top << " ";
  for (int i = 1; i <= top; ++i) {
    std::cout << query[i][0] << " " << query[i][1] << " ";
  }

  std::cout << std::endl;
  for (int i = 1; i <= top; ++i) {
    std::cin >> W[query[i][2]];
  }

  for (int i = 1; i <= N; ++i) {
    for (int j = i; j <= N; ++j) {
      if (lb[j][i]) {
        std::swap(lb[i], lb[j]);
        break;
      }
    }

    for (int j = 1; j <= N; ++j) {
      if (i == j) continue;
      if (lb[j][i]) {
        W[j] ^= W[i];
        lb[j] ^= lb[i];
      }
    }
  }

  std::cout << "! ";
  for (int i = 2; i <= N; ++i) {
    std::cout << W[i] << " ";
  }
  std::cout << std::endl;

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3656kb

input:

4 1
1 2
2 3
2 4
3 2

output:

YES
? 2 2 3 2 4 
! 7 3 0 

result:

wrong answer Wrong answer in node 2, expected "1", but found "7".