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