QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#813121#9866. Extracting Weightstest_algthWA 1ms3700kbC++172.8kb2024-12-13 22:16:462024-12-13 22:16:52

Judging History

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

  • [2024-12-13 22:16:52]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3700kb
  • [2024-12-13 22:16:46]
  • 提交

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) {
  // printf("edge : (%d, %d)\n", u, pa);
  dep[u] = dep[pa] + 1, fa[u] = pa;
  for (int v : adj[u]) {
    if (v == pa) continue;
    solve(v, u);
  }
}

inline int lca(int a, int b) {
  if (dep[a] < dep[b]) std::swap(a, b);
  // printf("(%d, %d)\n", dep[a], dep[b]);
  now.set(a), now.set(b);
  while (dep[a] > dep[b]) a = fa[a], now.set(a);
  // printf("lca : %d, %d\n", a, b);
  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]) && 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 >> K;
  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)];
      // printf("(%d %d) -> %d\n", i, j, lca(i, j));
      if (len != K) continue;
      
      int res = Insert();
      if (res != -1) {
        query[++top] = {i, j, res};//printf("(%d, %d)\n", i, j);
      }
    }
  }

  if (cnts < N) {
    std::cout << "NO" << std::endl;
    return 0;
  }

  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 = 1; j <= N; ++j) {
  //     std::cout << lb[i][j] << "  "[j == N];
  //   }
  //   std::cout << W[i] << '\n';
  // }

  for (int i = 1; i <= N; ++i) {
    for (int j = i; j <= N; ++j) {
      if (lb[j][i]) {
        std::swap(lb[i], lb[j]); std::swap(W[i], W[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];
      }
    }
  }

  // for (int i = 1; i <= N; ++i) {
  //   for (int j = 1; j <= N; ++j) {
  //     std::cout << lb[i][j] << " \n"[j == N];
  //   }
  // }

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

  return 0;
}

詳細信息

Test #1:

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

input:

4 1
1 2
2 3
2 4
1 3 2

output:

YES
? 3 1 2 2 3 2 4 
! 1 2 3 

result:

ok OK 3 numbers

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3652kb

input:

5 2
1 2
2 3
3 4
3 5
1 2 3 2

output:

YES
? 4 1 3 2 4 2 5 4 2 
! 1 0 3 2 

result:

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