QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#813112 | #9866. Extracting Weights | test_algth | WA | 1ms | 3656kb | C++17 | 2.2kb | 2024-12-13 22:02:34 | 2024-12-13 22:02:40 |
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) {
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".