QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#815707#9866. Extracting WeightsNana7WA 5ms12836kbC++142.7kb2024-12-15 16:37:122024-12-15 16:37:14

Judging History

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

  • [2024-12-15 16:37:14]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:12836kb
  • [2024-12-15 16:37:12]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<bitset> 
#include<vector>
#define I inline
using namespace std;

const int N = 260;
struct bool_Matrix{
	int n,m,x[N*N],id[N*N];
	bitset<N> a[N*N];
	I void init() {
		for(int i=1;i<=n;++i) a[i].reset(),x[i]=0;
		for(int i=1;i<=250*250;++i) id[i]=i;
		n=m=0;
	} 
	I int Gauss() {
	//	cout<<"!!"<<r<<endl;;
	//	for(int i=1;i<=n;++i) cout<<a[i]<<' '<<x[i]<<endl;
		int r=1;
		for(int i=1;i<=m&&r<=n;++i,++r) {
			int ps=r;
			for(int j=r+1;j<=n;++j) {
				if(a[j][i]) {
					ps=j;
				}
			}
			if(ps!=r) swap(x[ps],x[r]),swap(a[ps],a[r]),swap(id[ps],id[r]);
			if(!a[r][i]) {
				r--;
				continue;
			}
			
			for(int j=r+1;j<=n;++j) {
				if(a[j][i]) {
					a[j]^=a[r];
					x[j]^=x[r];
				}
			}
		}
		if(r<=m) {
			return m-r+1;
		}
		bool can=1;
		for(int i=r;i<=n;++i) {
			if(x[i]) can=0;
		}
		if(!can) return -1;
		
		for(int i=m;i>=1;--i) {
			for(int j=i-1;j>=1;--j) {
				if(a[j][i]) a[j]^=a[i],x[j]^=x[i];
			}
		}
		return 0;
	} 
}BM;
vector<int> q[N];
int n,k,dep[N],f[N];

void dfs(int x,int fa) {
	dep[x]=dep[fa]+1; f[x]=fa;
	for(auto &t:q[x]) {
		if(t==fa) continue;
		dfs(t,x);
	}
}
I vector<int> trans(int x,int y) {
	vector<int> ret; 
	if(x==y) {
		ret.push_back(x);
		return ret;
	}
	ret.push_back(x);
	ret.push_back(y);
	while(1) {
		if(dep[x]<dep[y]) swap(x,y);
		x=f[x]; 
		if(x==y) break; 
		ret.push_back(x);
	} 
	return ret;
}

#define pii pair<int,int>
int used[N*N];

I void solve() {
	cin>>n>>k; BM.init();
	for(int i=1;i<n;++i) {
		int x,y; cin>>x>>y;
		q[x].push_back(y);
		q[y].push_back(x);
	}
	dfs(1,0);
	BM.init(); BM.m=n;
	vector<pii> query,rq;
	for(int i=1;i<=n;++i) {
		for(int j=i;j<=n;++j) {
			vector<int> v=trans(i,j);
			if(v.size()==k+1) {
				query.push_back({i,j});
				BM.n++;
				for(auto &t:v) {
					BM.a[BM.n][t]=1;
				}
 			}
		}
	}
	BM.a[++BM.n][1]=1;
	bool_Matrix ck=BM,mk=BM;
	if(ck.Gauss()) {
		cout<<"NO"<<endl;
		cout.flush();
		return ;
	}
	for(int i=1;i<=n;++i) {
		used[ck.id[i]]=1;
	}
	
	int sz=0; BM.init(); BM.m=n;
	for(int i=0;i<query.size();++i) {
		if(used[i+1]) {
			sz++;
			rq.push_back(query[i]);
			BM.a[sz]=mk.a[i+1];
			BM.x[sz]=mk.x[i+1];
		}
	}
	
	cout<<"YES"<<endl;
	cout.flush();
	cout<<"? "<<sz<<' ';
	for(auto &t:rq) {
		cout<<t.first<<' '<<t.second<<' ';
	}
	cout<<endl;
	cout.flush();
	
	vector<int> v(sz+1);
	for(int i=1;i<=sz;++i) cin>>v[i],BM.x[i]=v[i];
	
	BM.Gauss();
	
	cout<<"! ";
	for(int i=2;i<=n;++i) cout<<BM.x[i]<<' '; cout<<endl;
	cout.flush();
	
}
/*
 4 1
 1 2
 2 3
 2 4
 1 3 2

*/
int main()
{
	solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 5ms
memory: 12836kb

input:

4 1
1 2
2 3
2 4
1 3 2

output:

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

result:

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