QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#813137#9866. Extracting Weightstest_algthRE 1ms3656kbC++172.8kb2024-12-13 22:25:442024-12-13 22:25:46

Judging History

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

  • [2024-12-13 22:25:46]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3656kb
  • [2024-12-13 22:25:44]
  • 提交

answer

#include <bits/stdc++.h>

const int MAXN = 255;
std::vector <int> adj[MAXN];
std::bitset <MAXN> lb[MAXN], now, cur;
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 (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() {
  cur = now;
  for (int i = 1; i <= N; ++i) {
    if (ok[i] && now[i] == 1) now ^= lb[i];
    if ((!ok[i]) && now[i]) {
      lb[i] = cur, ++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)];
      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;
      }
    }

    if (!lb[i][i]) assert(false);

    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: 3652kb

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: 0
Accepted
time: 1ms
memory: 3656kb

input:

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

output:

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

result:

ok OK 4 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

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

output:

NO

result:

ok Correct

Test #4:

score: -100
Runtime Error

input:

250 1
108 84
37 129
33 68
131 135
26 173
186 25
35 104
78 123
52 115
239 44
166 149
127 210
185 212
246 64
249 143
137 101
82 209
244 29
15 242
20 62
243 151
81 10
42 159
65 71
71 105
166 192
214 225
97 87
86 208
43 60
235 54
77 107
28 147
195 2
45 153
104 180
63 250
205 165
220 206
24 92
12 41
233 ...

output:

YES
? 249 1 233 2 195 2 197 3 134 3 162 4 16 4 72 5 140 5 240 6 156 6 207 7 16 7 99 8 106 8 213 9 56 9 110 10 81 10 126 11 30 11 128 12 41 12 107 13 174 13 218 14 121 14 235 15 223 15 242 17 161 17 177 18 173 18 197 19 171 19 181 20 62 20 205 21 27 21 249 22 102 22 218 23 153 23 182 24 78 24 92 25 3...

result: