QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#859619 | #9866. Extracting Weights | linxuanrui | WA | 1ms | 3712kb | C++14 | 2.1kb | 2025-01-17 21:12:38 | 2025-01-17 21:12:48 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 255;
int n,k,u,v,cnt,val[N],ans[N],tmp[N],x[N],tpos[N];
vector<int> g[N];
bitset<N << 1> a[N],t[N],now;
bool gauss(int n){
for(int i = 1;i <= n;i++){
int pos = 0;
for(int j = i;j <= n;j++){
if(t[j][i])pos = j;
}
if(!pos)return false;
swap(t[pos],t[i]),swap(val[pos],val[i]);
for(int j = 1;j <= n;j++){
if(j == i || !t[j][i])continue;
t[j] ^= t[i],val[j] ^= val[i];
// for(int k = i;k <= 2 * n;k++)a[j][k] ^= a[i][k];
}
// for(int i = 1;i <= n;i++){
// for(int j = 1;j <= n;j++)cout << t[i][j] << " ";
// cout << endl;
// }
// for(int i = 1;i <= n;i++)cout << val[i] << " ";cout << endl;
}
return true;
}
void add(int rt,int u){
bitset<N << 1> tmp = now;
for(int i = 1;i < n;i++){
if(tmp.test(i) && a[i].test(i)){
tmp ^= a[i];
}
}
int pos = tmp._Find_first();
if(pos < N){
a[pos] = tmp,t[pos] = now,x[rt] = u,tpos[pos] = rt;
// cout << now.to_ullong() << " " << tmp.to_ullong() << " " << rt << " " << u << endl;
}
}
void dfs(int rt,int u,int fa,int dep){
now.set(u);
if(x[rt])return;
if(dep == k)add(rt,u);
for(auto v : g[u]){
if(v != fa)dfs(rt,v,u,dep + 1);
}
now.reset(u);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for(int i = 1;i < n;i++)cin >> u >> v,g[u].push_back(v),g[v].push_back(u);
now.set(1);
a[1] = t[1] = now;
for(int i = 2;i <= n;i++)now.reset(),dfs(i,i,0,0);
for(int i = 1;i <= n;i++){
if(!a[i].test(i))return cout << "NO",0;
}
// for(int i = 1;i <= n;i++){
// for(int j = 1;j <= n;j++)cout << t[i][j] << " ";
// cout << endl;
// }
cout << "YES\n? " << n - 1 << " ";
for(int i = 2;i <= n;i++)cout << tpos[i] << " " << x[tpos[i]] << " ";
cout << endl;
cout.flush();
for(int i = 2;i <= n;i++)cin >> val[i];
assert(gauss(n));
// for(int i = 1;i <= n;i++){
// for(int j = 1;j <= n;j++)cout << t[i][j] << " ";
// cout << endl;
// }
cout << "! ";
for(int i = 2;i <= n;i++)cout << val[i] << " ";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
4 1 1 2 2 3 2 4 1 3 2
output:
YES ? 3 2 1 3 2 4 2 ! 1 2 3
result:
ok OK 3 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
5 2 1 2 2 3 3 4 3 5 2 4 1 3
output:
YES ? 4 2 4 4 5 3 1 5 2 ! 4 5 3 2
result:
ok OK 4 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
6 2 1 2 2 3 3 4 4 5 4 6
output:
NO
result:
ok Correct
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3584kb
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:
NO
result:
wrong answer Expected "YES", but found "NO"