QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#859412#9866. Extracting WeightslinxuanruiWA 1ms3840kbC++141.9kb2025-01-17 18:44:582025-01-17 18:45:02

Judging History

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

  • [2025-01-17 18:45:02]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3840kb
  • [2025-01-17 18:44:58]
  • 提交

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){
	cout << "! ";
	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: 1ms
memory: 3840kb

input:

4 1
1 2
2 3
2 4
1 3 2

output:

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

result:

wrong answer Wrong answer in node 2, expected "1", but found "3".