QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#813137 | #9866. Extracting Weights | test_algth | RE | 1ms | 3656kb | C++17 | 2.8kb | 2024-12-13 22:25:44 | 2024-12-13 22:25:46 |
Judging History
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...