QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#859639 | #9866. Extracting Weights | linxuanrui | WA | 0ms | 3712kb | C++14 | 2.1kb | 2025-01-17 21:19:24 | 2025-01-17 21:19:42 |
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> a[N],t[N],now;
vector<pair<int,int> > v2;
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> 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;
v2.push_back({rt,u});
// 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(auto i : v2)cout << i.first << " " << i.second << " ";
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: 3584kb
input:
4 1 1 2 2 3 2 4 1 3 2
output:
YES ? 3 2 1 2 3 2 4 ! 1 2 3
result:
ok OK 3 numbers
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3712kb
input:
5 2 1 2 2 3 3 4 3 5 2 3 1 4
output:
YES ? 4 2 4 2 5 3 1 4 5 ! 4 0 6 5
result:
wrong answer Wrong answer in node 3, expected "5", but found "0".