QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#815659#9866. Extracting WeightsNana7RE 11ms3852kbC++142.3kb2024-12-15 16:15:082024-12-15 16:15:11

Judging History

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

  • [2024-12-15 16:15:11]
  • 评测
  • 测评结果:RE
  • 用时:11ms
  • 内存:3852kb
  • [2024-12-15 16:15:08]
  • 提交

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];
	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: 3852kb

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: 0ms
memory: 3848kb

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: 3560kb

input:

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

output:

NO

result:

ok Correct

Test #4:

score: 0
Accepted
time: 11ms
memory: 3648kb

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:

YES
? 249 1 233 2 195 2 197 3 134 3 162 4 16 4 72 5 140 5 240 6 156 6 207 7 16 7 99 8 106 8 213 9 56 9 110 10 81 10 126 11 30 11 128 12 41 12 107 13 174 13 218 14 121 14 235 15 223 15 242 17 161 17 177 18 173 18 197 19 171 19 181 20 62 20 205 21 27 21 249 22 102 22 218 23 153 23 182 24 78 24 92 25 3...

result:

ok OK 249 numbers

Test #5:

score: 0
Accepted
time: 9ms
memory: 3528kb

input:

250 1
159 6
156 104
218 66
172 38
158 142
37 143
171 240
53 204
139 103
152 177
213 231
91 93
75 77
39 125
239 28
196 237
185 209
40 219
43 114
129 222
162 247
140 23
48 35
184 215
186 155
58 178
178 98
82 91
238 164
33 54
127 165
60 151
2 7
160 223
189 247
50 209
189 205
81 49
237 180
88 156
225 20...

output:

YES
? 249 1 60 1 72 2 7 2 168 3 237 4 92 4 93 5 56 5 166 6 159 6 230 8 184 8 214 9 106 10 93 10 103 11 155 12 100 12 179 13 194 13 208 14 184 14 219 15 112 15 137 15 148 16 70 16 86 17 101 17 225 18 56 19 68 19 158 20 119 20 160 20 217 21 131 22 142 23 140 23 245 24 117 24 230 25 139 25 242 26 56 26...

result:

ok OK 249 numbers

Test #6:

score: -100
Runtime Error

input:

250 2
138 236
154 181
103 227
74 169
248 123
25 69
26 157
250 216
164 75
89 215
93 43
76 56
56 153
88 139
121 72
130 228
231 198
224 75
238 235
66 8
119 77
129 204
125 30
204 165
113 60
156 14
226 192
54 201
61 70
59 62
11 233
60 44
240 177
79 152
88 13
137 26
186 133
94 134
180 246
167 126
61 79
10...

output:


result: