QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#811201#9866. Extracting WeightsshnshnWA 0ms5856kbC++142.4kb2024-12-12 16:27:062024-12-12 16:27:07

Judging History

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

  • [2024-12-12 16:27:07]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5856kb
  • [2024-12-12 16:27:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

//#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
const double PI = acos(-1);
const int N = 250 + 10;
const int mod = 1e9 + 7;

bool b[N][N];
vector<int>e[N],path;
bitset<252> bit[N*N],bit1[N*N];
int n,k;
int id=0;
vector<pii>c;

void dfs(int x,int fa,int num,int be){
	if(num==k){
		if(b[x][be]==0){
			id++;
			for(int y:path){
				bit[id][y]=1;
				bit1[id][y]=1;
			}
			b[x][be]=b[be][x]=1;
			bit[id][be]=1;
			bit1[id][be]=1;
			c.push_back({be,x});
		}
		return ;
	}
	for(int y:e[x]){
		if(fa==y)continue;
		path.push_back(y);
		dfs(y,x,num+1,be);
		path.pop_back();
	}
}

bool bb[N*N];
vector<int>a(N+1);

bool check(){
	
	for(int i=1;i<=n;i++){
		int p=-1;
		
//		cout<<"i="<<i<<endl;
//		for(int j=1;j<=id;j++){
//			cout<<bit[j]<<endl;
//		}
		
		for(int j=1;j<=id;j++){
			if(bb[j])continue;
			if(bit[j][i]==1){
				p=j;
				bb[j]=1;
				a[i]=j;
				break;
			}
		}
		if(p==-1){
			return 0;
		}
		for(int j=1;j<=id;j++){
			if(bb[j])continue;
			if(bit[j][i]==1){
				bit[j]^=bit[p];
			}
		}
	}
}

int w[N*N];

void check1(){
	memset(bb,0,sizeof bb);
	for(int i=1;i<=n;i++){
		int p=-1;
		for(int j=1;j<=id;j++){
			if(bb[j])continue;
			if(bit1[j][i]==1){
				p=j;
				bb[j]=1;
				break;
			}
		}
		
		for(int j=1;j<=id;j++){
			if(bb[j])continue;
			if(bit1[j][i]==1){
				bit1[j]^=bit1[p];
				w[j]^=w[p];
			}
		}
	}
	vector<int>ans(n+1);
	for(int i=n;i>1;i--){
		for(int j=i+1;j<=n;j++){
			if(bit1[a[i]][j]==1){
				w[a[i]]^=ans[j];
			}
			
		}
		ans[i]=w[a[i]];
	}
	cout<<"! ";
	for(int i=2;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	cout<<endl;
}

void solve() {
	cin>>n>>k;
	
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	bit[++id][1]=1;
	bit1[id][1]=1;
	c.push_back({0,0});
	c.push_back({1,1});
	for(int i=1;i<=n;i++){
		dfs(i,0,0,i);
	}
	bool f=check();
	if(f==0){
		cout<<"NO"<<endl;
	} else {
		cout<<"YES"<<endl;
		cout<<"? "<<n-1<<" ";
		for(int i=2;i<=n;i++){
			auto [x,y]=c[a[i]];
			cout<<x<<" "<<y<<" ";
		}
		cout<<endl;
		for(int i=2;i<=n;i++){
			cin>>w[a[i]];
		}
		
		check1();
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int T = 1;
	//cin>>T;
	while (T--) {
		solve();
	}
	
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 5856kb

input:

4 1
1 2
2 3
2 4

output:

NO

result:

wrong answer Expected "YES", but found "NO"