QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#859623#9866. Extracting WeightslinxuanruiWA 1ms3584kbC++142.0kb2025-01-17 21:14:592025-01-17 21:14:59

Judging History

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

  • [2025-01-17 21:14:59]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3584kb
  • [2025-01-17 21:14:59]
  • 提交

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;
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;
//		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: 0
Wrong Answer
time: 1ms
memory: 3584kb

input:

4 1
1 2
2 3
2 4
2 2 2

output:

YES
? 3 2 4 2 4 4 2 
! 2 0 0 

result:

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