QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#859439 | #9866. Extracting Weights | linxuanrui | WA | 2ms | 5248kb | C++14 | 2.1kb | 2025-01-17 19:06:09 | 2025-01-17 19:06:10 |
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],tmp[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 || !a[j][i])continue;
for(int k = i;k <= 2 * n;k++)a[j][k] ^= a[i][k];
}
}
return true;
}
void output(int n){
cout << "! ";
// for(int i = 1;i <= n;i++){
// for(int j = 1;j <= 2 * n;j++)cout << a[i][j] << " ";
// cout << endl;
// }
for(int t = 30;~t;t--){
for(int i = 1;i <= n;i++)tmp[i] = bool(val[i] & (1 << t));
for(int i = 1;i <= n;i++){
bool qwq = 0;
for(int j = 1;j <= n;j++)qwq ^= (a[i][j + n] && tmp[j]);
// cout << t << " " << i << " " << qwq << endl;
// cout << endl;
if(qwq)ans[i] |= (1 << t);
}
}
for(int i = 1;i <= n;i++)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 < 2 * 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: 100
Accepted
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 ! 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 3 1 2 4
output:
YES ? 4 2 5 3 1 4 2 5 4 ! 4 5 3 2
result:
ok OK 4 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 3584kb
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: 2ms
memory: 5248kb
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"