QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#806575#9866. Extracting Weightslimbo_nullTL 0ms0kbC++172.7kb2024-12-09 11:55:102024-12-09 11:55:11

Judging History

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

  • [2024-12-09 11:55:11]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-12-09 11:55:10]
  • 提交

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;
        cout.flush();
    } else {
        cout << "YES" << endl;
        cout << "? " << cnt;
        for (int i = 2; i <= n; ++i) {
            cout << " " << x[i] << ' ' << y[i];
        }
        cout << endl;
        cout.flush();

        for (int i = 2; i <= n; ++i) {
            cin >> val[i];
        }

        guassEliminate();

        cout << "!";
        for (int i = 2; i <= n; ++i) {
            cout << " " << val[i];
        }
        cout << endl;
        cout.flush();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

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

result: