QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#806571 | #9866. Extracting Weights | limbo_null | TL | 0ms | 0kb | C++17 | 2.6kb | 2024-12-09 11:53:00 | 2024-12-09 11:53:06 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 250 + 19;
using BitSet = bitset<N>;
BitSet base[N], raw_ask[N], tmp, mask;
int n, k, x[N], y[N], cnt, val[N];
vector<int> e[N];
int fa[N], dep[N];
void dfs(int u, int p) {
if (p) fa[u] = p;
for (auto v : e[u]) {
if (v != p) {
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
}
const BitSet& getAsk(int u, int v) {
BitSet& sub_ask = tmp;
sub_ask.reset();
if (dep[u] < dep[v]) swap(u, v);
while (dep[u] > dep[v]) {
sub_ask.set(u, 1);
u = fa[u];
}
while (u != v) {
sub_ask.set(u, 1);
sub_ask.set(v, 1);
u = fa[u];
v = fa[v];
}
sub_ask.set(u, 1);
return sub_ask;
}
void addBase(int u, int v) {
const BitSet& current_ask = getAsk(u, v);
if (current_ask.count() != k + 1) return;
mask = current_ask;
for (int i = 1; i <= n; ++i) {
if (base[i].any() && mask[i]) {
mask ^= base[i];
} else if (mask[i]) {
base[i] = mask;
raw_ask[i] = current_ask;
x[i] = u;
y[i] = v;
++cnt;
break;
}
}
}
void guassEliminate() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
if (raw_ask[i][j]) {
val[i] ^= val[j];
raw_ask[i] ^= raw_ask[j];
}
}
}
for (int i = n; i >= 1; --i) {
for (int j = i - 1; j >= 1; --j) {
if (raw_ask[j][i]) {
val[j] ^= val[i];
raw_ask[j] ^= raw_ask[i];
}
}
}
}
int main() {
// ios::sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
base[1].set(1, 1);
raw_ask[1].set(1, 1);
cnt = 1;
for (int u = 1; u <= n; ++u) {
for (int v = u + 1; v <= n; ++v) {
addBase(u, v);
}
}
if (cnt != n) {
cout << "NO" << endl;
} else {
cout << "YES" << endl;
cout << "? " << cnt;
for (int i = 2; i <= n; ++i) {
cout << " " << x[i] << ' ' << y[i];
}
cout << endl;
for (int i = 2; i <= n; ++i) {
cin >> val[i];
}
guassEliminate();
cout << "!";
for (int i = 2; i <= n; ++i) {
cout << " " << val[i];
}
cout << endl;
}
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
4 1 1 2 2 3 2 4
output:
YES ? 4 1 2 2 3 2 4