QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#859410 | #9866. Extracting Weights | linxuanrui | WA | 0ms | 3840kb | C++14 | 1.9kb | 2025-01-17 18:43:51 | 2025-01-17 18:43:58 |
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,fa[N][N],x[N],a[N][N << 1],ans[N],val[N];
vector<int> g[N],t[N];
bool gauss(int n){
// 求逆矩阵
for(int i = 1;i <= n;i++)a[i][i + n] = 1;
// for(int i = 1;i <= n;i++){
// for(int j = 1;j <= 2 * n;j++)cout << a[i][j] << " ";
// cout << endl;
// }
for(int i = 1;i <= n;i++){
int pos = 0;
for(int j = i;j <= n;j++){
if(a[j][i])pos = j;
}
if(!pos)return false;
for(int j = i;j <= 2 * n;j++){
swap(a[i][j],a[pos][j]);
}
for(int j = 1;j <= n;j++){
if(j == i)continue;
int t = (a[i][i] * a[j][i]);
for(int k = i;k <= 2 * n;k++)a[j][k] ^= (a[i][k] * t);
}
}
// for(int i = 1;i <= n;i++){
// for(int j = 1;j <= 2 * n;j++)cout << a[i][j] << " ";
// cout << endl;
// }
return true;
}
void output(int n){
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++)ans[i] ^= (a[i][j + n] * val[j]);
cout << ans[i] << " ";
}
}
void dfs(int rt,int u,int f,int dep){
fa[rt][u] = f;
if(dep == k)t[rt].push_back(u);
for(auto v : g[u]){
if(v == f)continue;
dfs(rt,v,u,dep + 1);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
mt19937_64 rnd(time(0));
cin >> n >> k;
for(int i = 1;i < n;i++)cin >> u >> v,g[u].push_back(v),g[v].push_back(u);
for(int i = 1;i <= n;i++)dfs(i,i,0,0);
for(int _ = 1;_ <= 10;_++){
for(int i = 2;i <= n;i++){
if(!t[i].size())return cout << "NO",0;
x[i] = t[i][rnd() % t[i].size()];
for(int j = 1;j < n;j++)a[i - 1][j] = 0;
a[i - 1][i - 1] = 1;
int t = x[i];
while(t)a[i - 1][t - 1] = true,t = fa[i][t];
}
if(gauss(n - 1)){
cout << "YES\n? " << n - 1 << " ";
for(int i = 2;i <= n;i++)cout << i << " " << x[i] << " ";
cout << endl;
cout.flush();
for(int i = 1;i < n;i++)cin >> val[i];
output(n - 1);
return 0;
}
}
cout << "NO";
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3840kb
input:
4 1 1 2 2 3 2 4 1 3 2
output:
YES ? 3 2 1 3 2 4 2 0 3 1
result:
wrong answer Token "0" doesn't correspond to pattern "!"