QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#815657#9866. Extracting WeightsNana7RE 1ms3804kbC++142.3kb2024-12-15 16:14:292024-12-15 16:14:34

Judging History

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

  • [2024-12-15 16:14:34]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3804kb
  • [2024-12-15 16:14:29]
  • 提交

answer

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

const int N = 111;
struct bool_Matrix{
	int n,m,x[N];
	bitset<N> a[N];
	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]);
			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>
I void solve() {
	cin>>n>>k;
	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.m=n;
	vector<pii> query;
	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;
	if(ck.Gauss()) {
		cout<<"NO"<<endl;
		cout.flush();
		return ;
	}
	
	int sz= query.size();
	cout<<"YES"<<endl;
	cout.flush();
	cout<<"? "<<sz<<' ';
	for(auto &t:query) {
		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: 100
Accepted
time: 1ms
memory: 3804kb

input:

4 1
1 2
2 3
2 4
1 3 2

output:

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

result:

ok OK 3 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 3524kb

input:

5 2
1 2
2 3
3 4
3 5
1 2 3 4

output:

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

result:

ok OK 4 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

6 2
1 2
2 3
3 4
4 5
4 6

output:

NO

result:

ok Correct

Test #4:

score: -100
Runtime Error

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:


result: