QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#865226#9866. Extracting Weightslw22005WA 1ms3840kbC++141.4kb2025-01-21 16:12:072025-01-21 16:12:07

Judging History

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

  • [2025-01-21 16:12:07]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3840kb
  • [2025-01-21 16:12:07]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=310;
int n,k,a,b,cnt,h[N],c[N],d[N];
bitset<310>tmp,s[N],t[N],t1[N];
struct AB{
	int x,y,n;
}l[N*2];
void in(int x,int y){
	l[++cnt].x=x,l[cnt].y=y;
	l[cnt].n=h[x],h[x]=cnt;
}
void add(int p,int rt){
	tmp=s[p];
	for(int i=n;i>=1;i--){
		if(!s[p][i])continue;
		else{
			if(t[i][i]){
				s[p]^=t[i];
				if(s[p]==s[0])break;
			}else{
				t[i]=s[p],t1[i]=tmp;
				c[i]=p,d[i]=rt;
				break;
			}
		}
	}
}
void dfs(int a,int p,int st,int rt){
	int b;
	s[a]=s[p],s[a].set(a);
	if(st==k){
		add(a,rt);
		return ;
	}
	for(int i=h[a];i;i=l[i].n){
		b=l[i].y;
		if(b==p)continue;
		dfs(b,a,st+1,rt);
	}
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		in(a,b),in(b,a);
	}
	s[0].reset();
	for(int i=1;i<=n;i++){
		dfs(i,0,0,i);
	}
	t[1].set(1),t1[1]=t[1];
	for(int i=1;i<=n;i++){
		if(t[i][i]==0){
			cout<<"NO"<<endl;
			return 0;
		}
	}
	cout<<"YES"<<endl;
	cout<<"? "<<n-1<<' ';
	for(int i=2;i<=n;i++){
		cout<<c[i]<<' '<<d[i]<<' ';
	}
	cout<<endl;
	for(int i=2;i<=n;i++){
		cin>>c[i];
	}
	for(int i=n;i>=1;i--){
		for(int j=i-1;j>=1;j--){
			if(t1[j][i])t1[j]^=t1[i],c[j]^=c[i];
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			if(t1[i][j])c[i]^=c[j];
		}
	}
	cout<<"! ";
	for(int i=2;i<=n;i++)cout<<c[i]<<' ';
	cout<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3840kb

input:

4 1
1 2
2 3
2 4
1 3 2

output:

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

result:

ok OK 3 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

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

output:

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

result:

ok OK 4 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

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

output:

NO

result:

ok Correct

Test #4:

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

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 248 203 233 176 207 195 230 215 156 122 16 7 163 139 245 140 231 198 129 99 205 165 217 174 250 220 225 214 16 4 208 126 197 18 212 185 210 127 249 143 218 22 227 158 243 169 213 91 173 26 27 21 145 142 232 90 30 11 238 196 115 114 204 100 219 178 172 168 226 41 128 37 38 25 194 96 40 28 4...

result:

ok OK 249 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 3712kb

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 237 196 237 180 243 154 228 222 216 207 7 2 204 194 116 79 93 10 231 213 179 113 201 97 184 14 151 148 225 205 240 171 56 18 223 206 191 179 239 162 158 142 238 164 230 24 139 103 56 26 194 27 106 80 182 129 238 68 221 141 115 65 214 54 220 131 35 31 245 135 112 99 186 155 159 125 219 40 8...

result:

ok OK 249 numbers

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 3840kb

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:

YES
? 249 173 134 153 63 200 92 139 13 84 33 121 95 184 112 104 52 88 10 131 56 230 210 173 13 188 108 155 152 172 69 151 17 141 18 217 105 236 144 166 114 215 146 187 23 227 135 117 25 137 46 153 76 224 28 25 6 232 50 172 31 104 32 33 29 51 34 189 76 193 111 195 93 247 85 87 39 166 40 123 76 182 42...

result:

wrong answer Wrong answer in node 30, expected "1043155115", but found "1043155053".