QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#802939#9866. Extracting Weightsucup-team3802#WA 2ms4176kbC++233.1kb2024-12-07 15:17:012024-12-07 15:17:01

Judging History

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

  • [2024-12-07 15:17:01]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4176kb
  • [2024-12-07 15:17:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(ll i = (l); i < (r); ++i)
#define all(X) (X).begin(), (X).end()
using ll = long long;

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> g(n);
    vector<vector<int>> dist(n, vector<int>(n, 10000));
    rep(i, 0, n - 1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    struct Bit {
        bitset<250> bit;
        int u;
        int v;
    };
    vector<Bit> mat;
    mat.push_back(Bit{bitset<250>(1), -1, -1});
    map<pair<int, int>, bitset<250>> mp;

    auto dfs = [&](auto self, int v, vector<int>& vec) -> void {
        if(vec.size() == k) {
            if(vec[0] < v) {
                bitset<250> bit;
                for(int x : vec) bit.set(x, true);
                bit.set(v, true);
                mat.push_back(Bit{bit, vec[0], v});
                mp[{vec[0], v}] = bit;
            }
        } else {
            int p = -1;
            if(!vec.empty()) p = vec[0];
            vec.push_back(v);
            for(int u : g[v]) {
                if(p != u) {
                    self(self, u, vec);
                }
            }
            vec.pop_back();
        }
    };
    vector<int> tmp;
    rep(i, 0, n) { dfs(dfs, i, tmp); }

    // for(auto [bit, u, v] : mat) {
    //     cout << u << " " << v << endl;
    // }

    int rank = 0;
    rep(j, 0, n) {
        rep(i, rank, mat.size()) {
            if(mat[i].bit[j]) {
                swap(mat[rank], mat[i]);
                break;
            }
        }
        if(mat[rank].bit[j]) {
            rep(i, 0, mat.size()) {
                if(rank != i && mat[i].bit[j]) {
                    mat[i].bit ^= mat[rank].bit;
                }
            }
            rank++;
        }
    }

    if(rank < n) {
        cout << "NO" << endl;
        return 0;
    }

    vector<pair<int, int>> query;
    rep(i, 1, n) {
        auto [bit, u, v] = mat[i];
        query.emplace_back(u, v);
    }

    cout << "YES" << endl;
    cout << "? " << query.size();
    for(auto [u, v] : query) {
        cout << " " << u + 1 << " " << v + 1;
    }
    cout << endl;

    vector<int> res(query.size());
    rep(i, 0, query.size()) cin >> res[i];

    vector<pair<bitset<250>, int>> mat2;
    mat2.emplace_back(bitset<250>(1), 0);
    rep(i, 0, query.size()) {
        auto [u, v] = query[i];
        mat2.emplace_back(mp[{u, v}], res[i]);
    }

    rank = 0;
    rep(j, 0, n) {
        rep(i, rank, mat2.size()) {
            if(mat2[i].first[j]) {
                swap(mat2[rank], mat2[i]);
                break;
            }
        }
        if(mat2[rank].first[j]) {
            rep(i, 0, mat2.size()) {
                if(rank != i && mat2[i].first[j]) {
                    mat2[i].first ^= mat2[rank].first;
                    mat2[i].second ^= mat2[rank].second;
                }
            }
            rank++;
        }
    }

    cout << "!";
    rep(i, 1, n) cout << " " << mat2[i].second;
    cout << endl;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3552kb

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: 0ms
memory: 3616kb

input:

5 2
1 2
2 3
3 4
3 5
1 4 2 3

output:

YES
? 4 1 3 4 5 2 4 2 5
! 4 5 3 2

result:

ok OK 4 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

6 2
1 2
2 3
3 4
4 5
4 6

output:

NO

result:

ok Correct

Test #4:

score: 0
Accepted
time: 1ms
memory: 3944kb

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 2 195 3 162 4 72 5 140 6 207 7 99 8 106 9 110 10 81 11 30 12 41 13 174 14 235 15 242 7 16 17 177 18 173 19 171 20 62 21 249 22 218 23 153 24 92 25 186 26 173 21 27 28 147 29 244 11 128 31 172 32 52 33 68 34 164 35 104 36 226 37 129 25 38 39 194 28 40 12 107 42 159 43 60 44 239 45 153 46 10...

result:

ok OK 249 numbers

Test #5:

score: 0
Accepted
time: 1ms
memory: 4176kb

input:

250 1
159 6
156 104
218 66
172 38
158 142
37 143
171 240
53 204
139 103
152 177
213 231
91 93
75 77
39 125
239 28
196 237
185 209
40 219
43 114
129 222
162 247
140 23
48 35
184 215
186 155
58 178
178 98
82 91
238 164
33 54
127 165
60 151
2 7
160 223
189 247
50 209
189 205
81 49
237 180
88 156
225 20...

output:

YES
? 249 2 7 3 237 4 92 5 56 6 159 2 168 8 214 9 106 10 103 11 155 12 179 13 194 14 184 15 112 16 86 17 101 18 56 19 68 20 217 21 131 22 142 23 140 24 230 25 139 26 56 27 224 28 239 29 182 30 238 31 221 32 200 33 54 34 162 31 35 36 108 37 143 38 172 39 125 40 219 41 86 42 160 43 114 44 230 33 45 46...

result:

ok OK 249 numbers

Test #6:

score: 0
Accepted
time: 2ms
memory: 3944kb

input:

250 2
138 236
154 181
103 227
74 169
248 123
25 69
26 157
250 216
164 75
89 215
93 43
76 56
56 153
88 139
121 72
130 228
231 198
224 75
238 235
66 8
119 77
129 204
125 30
204 165
113 60
156 14
226 192
54 201
61 70
59 62
11 233
60 44
240 177
79 152
88 13
137 26
186 133
94 134
180 246
167 126
61 79
10...

output:

YES
? 249 2 10 3 56 4 106 5 88 6 25 7 72 8 184 9 18 2 88 11 34 12 115 13 139 14 171 15 241 16 70 17 23 9 141 19 210 20 72 21 147 22 174 17 187 1 24 6 29 26 225 27 248 28 164 6 117 28 125 29 33 32 52 29 84 11 51 35 56 36 110 37 90 38 242 9 39 40 166 41 248 42 105 10 93 44 113 18 45 19 46 47 124 11 63...

result:

ok OK 249 numbers

Test #7:

score: -100
Wrong Answer
time: 2ms
memory: 3984kb

input:

250 3
208 175
120 43
87 33
248 90
78 198
220 229
177 17
239 236
142 187
48 35
233 214
53 14
12 184
126 227
77 113
202 41
152 12
108 19
69 136
168 163
176 57
179 110
159 211
28 103
102 137
180 156
165 101
87 150
89 132
38 151
242 49
81 165
127 185
41 127
115 215
11 29
216 92
215 34
145 75
141 45
235 ...

output:

YES
? 249 2 53 1 3 4 69 5 182 6 63 7 242 8 124 9 35 10 99 11 29 12 85 7 20 2 200 15 19 16 176 9 17 18 176 19 108 7 20 16 164 10 22 23 62 24 153 8 124 22 26 10 180 28 45 11 238 30 155 31 181 32 242 6 134 34 215 9 233 16 165 2 37 38 151 11 65 22 235 30 41 6 42 17 43 44 175 12 45 30 226 4 47 35 214 13 ...

result:

wrong answer Expected "NO", but found "YES"