QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#421420#961. Smol Vertex CovercqbzlyWA 354ms6732kbC++203.1kb2024-05-25 18:25:092024-05-25 18:25:09

Judging History

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

  • [2024-05-25 18:25:09]
  • 评测
  • 测评结果：WA
  • 用时：354ms
  • 内存：6732kb
查看
  • [2024-05-25 18:25:09]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
const int N=505;
int T,n,m,cnt,used[N],to[N],bl[N],fa[N],sb;
int low[N],dfn[N],num,fk[N],vs[N];
stack<int>stk;
vector<int>G[N];
vector<int>G0[N]; 
pair<int,int>a[N*N];
pair<int,int>p[N];
mt19937 gen(time(0));
bool dfs(int u){
	used[u]=1;
	shuffle(G[u].begin(),G[u].end(),gen);
	for(auto v:G[u]){
		if(used[v])continue;
		used[v]=1;
		int x=to[v];
		to[u]=v,to[v]=u,to[x]=0;
		if(!x||dfs(x))return 1;
		to[v]=x,to[x]=v,to[u]=0;
	}
	return 0;
}
void init(){
	for(int i=1;i<=2*cnt;i++)fa[i]=i,dfn[i]=low[i]=fk[i]=vs[i]=0,G0[i].clear();num=sb=0;
}
void add(int x,int y){
	G0[x].pb(y);
}
void work(int u,int v){
	if(!bl[u]){
		if(v==p[bl[v]].fi)add(bl[v]+cnt,bl[v]);
		else add(bl[v],bl[v]+cnt);
	}
	else if(!bl[v]){
		if(u==p[bl[u]].fi)add(bl[u]+cnt,bl[u]);
		else add(bl[u],bl[u]+cnt);
	}
	else{
		int x=(u==p[bl[u]].se),y=(v==p[bl[v]].se);
		add(bl[u]+(1-x)*cnt,bl[v]+y*cnt);
		add(bl[v]+(1-y)*cnt,bl[u]+x*cnt); 
	}
}
void tarjan(int u){
	low[u]=dfn[u]=++num,stk.push(u),vs[u]=1;
	for(auto v:G0[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vs[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u]){
		int tmp=0;sb++;
		do{
			tmp=stk.top(),stk.pop();
			fk[tmp]=sb,vs[tmp]=0;
		}while(tmp!=u);
	}
}
int main(){
	//freopen("data.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
//	cin>>T;
//	while(T--){
		cin>>n>>m;for(int i=1;i<=n;i++)G[i].clear(),bl[i]=0;
		for(int i=1;i<=m;i++){
			int u,v;cin>>u>>v;
			G[u].pb(v),G[v].pb(u);
			//cout<<"edge:"<<u<<" "<<v<<"\n";
			a[i]={u,v};
		}
		for(int i=1;i<=n;i++)to[i]=0;
		for(int i=1;i<=n;i++){
			if(!to[i]){
				for(int j=1;j<=n;j++)used[j]=0;
				dfs(i);
			}
		}
		cnt=0;
		for(int i=1;i<=n;i++){
			if(to[i]&&i<to[i]){
				p[++cnt]={i,to[i]};
				bl[i]=bl[to[i]]=cnt;
			}
		}
		// for(int i=1;i<=n;i++){
		// 	cout<<p[i].fi<<" "<<p[i].se<<"\n";
		// }
		init();
		for(int i=1;i<=m;i++){
			int u=a[i].fi,v=a[i].se;
			if(bl[u]==bl[v])continue;
			work(u,v);
		}
		for(int i=1;i<=cnt*2;i++)if(!dfn[i])tarjan(i);
		bool ok=1;
		for(int i=1;i<=cnt;i++)if(fk[i]==fk[i+cnt])ok=0;
		if(ok){
			cout<<cnt<<"\n";
			for(int i=1;i<=cnt;i++){
				if(fk[i]<fk[i+cnt])cout<<p[i].fi<<" ";
				else cout<<p[i].se<<" ";
			}
			cout<<"\n";
		}
		else{
			bool flg=0;
			for(int i=1;i<=cnt;i++){
				init();
				for(int j=1;j<=m;j++){
					int u=a[j].fi,v=a[j].se;
					if(bl[u]==i||bl[v]==i||bl[u]==bl[v])continue;
					work(u,v);
				}
				for(int j=1;j<=cnt*2;j++)if(!dfn[j])tarjan(j);
				bool ok=1;
				for(int j=1;j<=cnt;j++)if(fk[j]==fk[j+cnt])ok=0;
				if(ok){
					flg=1;
					cout<<cnt+1<<"\n";
					for(int j=1;j<=cnt;j++){
						if(j==i)cout<<p[j].fi<<" "<<p[j].se<<" ";
						else if(fk[j]<fk[j+cnt])cout<<p[j].fi<<" ";
						else cout<<p[j].se<<" ";
					}
					cout<<"\n";
					break;
				}
			}
			if(!flg)cout<<"not smol"<<"\n";
		}
//	}
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3980kb

input:

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

output:

3
1 5 3

result:

ok vertex cover of size 3

Test #2:

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

input:

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

output:

not smol

result:

ok not smol

Test #3:

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

input:

3 0

output:

0

result:

ok vertex cover of size 0

Test #4:

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

input:

10 10
2 5
3 8
3 10
6 9
1 4
2 6
2 3
4 6
7 10
4 7

output:

5
1 2 3 6 7

result:

ok vertex cover of size 5

Test #5:

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

input:

10 20
1 9
3 6
3 7
8 9
3 8
1 4
5 10
7 10
4 6
7 9
9 10
2 7
1 6
5 8
2 9
1 7
5 7
3 10
2 6
4 10

output:

6
1 7 2 10 6 8

result:

ok vertex cover of size 6

Test #6:

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

input:

50 100
29 49
1 43
12 49
31 46
6 42
25 29
27 37
2 39
3 43
34 43
4 38
2 40
9 14
7 20
22 31
9 42
3 31
36 49
23 33
17 18
34 47
20 36
11 24
5 17
6 29
21 22
5 41
19 28
31 37
8 47
8 42
8 28
1 48
31 41
6 32
14 36
32 42
27 47
1 40
6 30
26 49
9 44
12 22
30 46
9 11
11 28
18 32
13 15
17 44
16 29
17 42
4 21
17 2...

output:

not smol

result:

ok not smol

Test #7:

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

input:

50 300
18 29
25 33
13 27
22 38
43 50
9 47
36 43
15 33
33 36
23 39
17 46
28 35
40 49
24 26
15 30
39 43
9 48
2 4
7 20
13 21
35 40
2 46
12 22
17 33
9 49
17 32
15 28
24 32
7 38
12 32
18 37
13 30
4 24
5 22
6 17
4 26
3 13
5 29
27 34
1 12
16 22
3 14
1 21
22 27
20 49
9 34
18 36
40 42
21 33
44 45
2 49
13 37
...

output:

not smol

result:

ok not smol

Test #8:

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

input:

50 1000
3 35
32 34
2 24
3 10
15 34
9 45
16 24
7 10
15 39
38 40
17 45
21 35
18 36
15 50
22 29
34 40
3 36
43 50
17 19
7 30
27 44
12 48
9 18
14 20
16 30
1 34
20 35
19 33
2 27
13 20
19 32
38 48
27 37
4 28
5 45
6 43
1 36
9 13
4 18
14 32
10 38
3 44
8 47
6 41
18 38
13 40
18 28
40 47
15 18
42 48
15 47
31 36...

output:

not smol

result:

ok not smol

Test #9:

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

input:

200 300
64 134
92 154
82 142
33 198
26 185
24 74
32 144
26 118
113 122
98 130
74 84
70 184
45 181
44 136
44 134
67 185
77 160
21 50
80 181
62 78
196 199
37 174
91 105
17 74
158 166
26 172
70 129
128 133
152 173
15 86
37 67
55 91
45 74
60 141
179 184
22 168
65 161
62 67
117 152
174 181
35 99
80 103
3...

output:

not smol

result:

ok not smol

Test #10:

score: 0
Accepted
time: 2ms
memory: 3884kb

input:

200 1000
19 159
64 180
15 88
82 136
22 57
92 200
86 87
176 194
57 106
116 179
101 128
27 137
41 71
35 139
48 153
177 178
80 131
9 156
29 122
101 148
88 163
90 116
16 72
8 166
100 116
97 161
19 143
78 163
23 119
104 146
91 161
52 66
183 196
29 123
84 86
41 109
65 76
82 161
138 182
108 156
35 94
101 1...

output:

not smol

result:

ok not smol

Test #11:

score: 0
Accepted
time: 7ms
memory: 3932kb

input:

200 5000
60 81
22 145
156 181
27 44
49 89
69 176
61 64
16 199
46 50
75 103
26 168
6 35
60 75
51 117
41 105
20 154
69 100
75 195
22 115
67 72
170 190
31 115
10 200
51 129
14 147
161 163
9 72
22 113
70 87
112 184
28 81
178 197
72 180
171 192
71 116
71 174
30 95
20 157
50 125
142 184
18 130
82 110
65 1...

output:

not smol

result:

ok not smol

Test #12:

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

input:

500 300
201 309
17 37
39 176
416 493
86 475
163 215
127 283
122 274
107 412
7 93
294 434
335 360
50 87
364 372
55 192
341 411
236 299
286 349
79 208
137 470
141 421
21 324
4 165
232 473
367 397
400 475
30 77
177 435
116 133
115 281
416 482
198 498
300 410
173 457
176 450
157 179
402 425
219 486
39 3...

output:

147
3 4 5 6 7 94 176 12 354 399 17 18 20 21 22 410 24 202 181 30 32 34 39 109 43 44 242 46 349 86 49 50 285 52 54 55 394 481 313 60 64 459 67 68 483 188 73 76 78 208 294 82 85 91 92 95 96 99 101 201 107 395 110 113 183 115 116 118 120 121 122 443 127 128 345 159 470 140 421 403 146 370 151 152 179 1...

result:

ok vertex cover of size 147

Test #13:

score: 0
Accepted
time: 2ms
memory: 3824kb

input:

500 1000
232 237
263 478
147 353
131 318
45 109
218 452
377 436
61 326
29 372
394 484
72 374
312 449
451 461
26 113
25 188
21 282
453 484
261 295
449 489
225 422
125 168
123 449
23 211
251 484
40 185
38 304
6 337
71 142
287 356
315 413
185 411
68 111
453 457
70 187
20 183
107 361
324 466
277 483
10 ...

output:

not smol

result:

ok not smol

Test #14:

score: 0
Accepted
time: 16ms
memory: 4268kb

input:

500 5000
78 84
13 468
95 135
258 447
258 267
226 321
132 282
238 355
194 248
75 485
325 390
46 182
156 284
272 289
204 361
15 228
322 448
410 430
35 317
227 386
325 398
207 443
36 280
73 153
117 459
396 494
234 430
140 199
49 357
26 128
177 210
15 231
351 379
357 484
299 489
376 454
177 377
228 331
...

output:

not smol

result:

ok not smol

Test #15:

score: 0
Accepted
time: 354ms
memory: 6732kb

input:

500 124750
260 435
24 351
41 342
79 458
63 342
463 485
313 372
88 486
300 435
144 440
88 480
83 373
126 356
129 486
118 416
83 138
439 447
59 222
1 162
367 487
137 286
253 261
255 451
329 461
276 328
66 184
76 441
228 492
93 396
288 420
2 424
257 318
216 342
249 474
152 200
206 485
13 332
353 406
20...

output:

not smol

result:

ok not smol

Test #16:

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

input:

20 20
12 17
15 18
14 20
3 19
11 12
5 14
6 20
2 6
13 19
6 18
3 20
13 18
8 19
1 9
4 12
1 5
10 14
10 13
10 12
7 11

output:

9
1 2 20 12 14 11 19 10 18

result:

ok vertex cover of size 9

Test #17:

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

input:

20 40
5 12
10 17
9 15
4 7
8 17
11 12
6 16
8 11
1 15
14 18
9 17
1 6
8 14
3 5
10 15
4 18
3 20
9 14
7 19
2 12
9 19
6 18
10 20
4 13
3 14
4 8
17 18
3 15
18 20
1 17
5 9
7 14
4 9
7 20
6 7
2 7
8 15
13 15
4 16
2 18

output:

10
1 18 3 13 12 16 7 8 9 10

result:

ok vertex cover of size 10

Test #18:

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

input:

20 70
3 4
4 8
7 17
2 7
5 7
3 15
1 16
5 10
13 20
10 19
7 15
8 9
6 16
11 20
18 19
3 5
6 17
1 5
9 11
4 12
15 18
1 15
18 20
5 18
8 14
1 14
10 20
8 17
7 9
13 14
6 14
11 19
4 7
5 8
13 19
4 6
6 9
2 18
10 14
2 10
6 20
12 14
10 15
2 8
1 19
14 18
11 17
3 9
16 18
1 17
11 16
6 19
7 19
13 16
8 19
7 14
12 15
1 2
...

output:

10
1 3 12 10 6 7 8 18 11 13

result:

ok vertex cover of size 10

Test #19:

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

input:

110 50
48 64
54 66
9 76
53 54
54 99
50 100
98 100
48 83
48 63
16 103
87 110
14 110
45 57
71 103
99 103
11 54
38 110
57 102
29 110
2 107
44 110
94 100
9 46
24 32
47 88
36 57
24 34
63 100
12 48
59 103
9 15
2 103
21 57
54 62
12 103
47 108
11 107
54 106
47 75
9 64
24 95
38 100
78 107
48 60
2 9
9 59
39 4...

output:

10
110 107 9 54 48 103 57 24 100 47

result:

ok vertex cover of size 10

Test #20:

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

input:

110 300
43 59
21 78
41 53
8 37
51 55
10 58
36 81
51 105
8 104
69 101
15 84
8 29
4 69
8 83
53 54
51 54
64 69
61 69
50 53
15 46
43 47
51 108
29 69
57 81
16 18
51 109
8 99
18 37
1 43
10 96
15 95
10 14
15 107
8 50
36 51
51 78
81 94
10 66
12 51
69 102
43 63
27 81
8 72
15 44
14 53
43 54
28 69
43 68
69 108...

output:

10
53 21 81 10 51 8 15 43 18 69

result:

ok vertex cover of size 10

Test #21:

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

input:

110 700
42 93
34 45
52 109
26 102
34 100
34 43
57 87
33 34
25 88
42 50
34 62
36 95
60 106
21 87
81 87
99 106
42 56
1 8
78 87
25 48
42 43
8 68
8 104
14 42
13 34
35 109
99 109
39 42
35 102
26 106
42 57
22 42
97 102
1 95
95 100
45 102
31 102
22 34
59 87
82 96
20 106
25 69
8 77
13 25
25 63
49 96
34 57
8...

output:

10
8 87 42 95 96 106 25 34 102 109

result:

ok vertex cover of size 10

Test #22:

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

input:

200 500
9 78
21 41
6 189
106 172
73 198
124 154
71 111
24 77
3 22
193 194
143 187
147 192
11 127
35 49
5 60
139 161
52 96
14 51
28 163
57 105
12 154
155 159
153 187
130 133
71 132
15 95
5 29
119 153
78 96
117 159
69 170
180 188
147 151
28 62
3 142
52 77
1 192
62 68
75 135
8 191
145 187
114 157
91 14...

output:

100
1 93 3 4 5 189 7 125 121 10 12 128 63 15 91 129 100 164 20 55 42 61 24 25 26 41 167 116 32 142 49 46 109 37 38 39 73 43 44 45 47 147 78 51 52 158 118 112 127 106 62 64 65 84 67 170 72 117 135 81 123 171 86 87 88 89 90 145 139 197 104 174 105 173 132 111 195 157 119 150 122 124 126 130 186 177 13...

result:

ok vertex cover of size 100

Test #23:

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

input:

200 3000
109 154
86 90
5 157
30 132
114 162
133 160
88 151
40 112
33 36
76 142
69 171
81 118
115 144
65 128
33 192
178 182
44 91
51 98
94 111
29 122
62 109
8 72
122 195
165 175
74 104
116 126
94 114
139 170
6 192
168 169
67 190
59 64
110 186
62 148
49 180
33 141
81 88
102 165
1 120
116 180
33 111
34...

output:

100
1 3 4 157 119 199 8 11 57 12 185 153 53 16 113 19 172 70 48 23 24 25 26 27 28 29 30 31 192 43 108 35 36 196 138 193 115 89 114 173 45 46 187 49 158 51 61 55 58 88 60 62 174 64 118 85 80 78 71 142 73 152 75 154 103 170 82 83 179 86 87 164 91 155 111 184 195 101 104 105 143 112 116 135 141 128 189...

result:

ok vertex cover of size 100

Test #24:

score: 0
Accepted
time: 2ms
memory: 4076kb

input:

200 8000
149 157
84 176
17 73
100 132
25 181
171 200
16 35
5 78
97 126
113 171
24 184
117 143
40 108
96 192
9 139
109 179
101 161
114 127
156 167
14 161
128 156
71 190
51 183
51 140
74 104
119 151
65 71
158 174
138 161
160 192
9 158
27 67
55 162
100 102
159 174
63 81
47 195
40 148
36 121
107 181
33 ...

output:

100
1 2 196 139 5 65 7 190 182 10 11 20 152 163 133 16 83 98 19 21 123 24 29 73 28 30 31 32 110 57 195 36 37 38 177 89 41 42 59 100 183 46 192 194 62 105 52 135 54 199 60 58 61 69 67 104 127 72 112 75 140 108 159 79 80 81 167 126 85 86 148 176 91 161 155 171 115 119 185 109 116 111 118 128 117 120 1...

result:

ok vertex cover of size 100

Test #25:

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

input:

500 500
271 342
280 463
424 444
322 342
200 239
239 358
449 469
239 269
54 63
98 342
375 488
245 449
338 342
18 63
188 359
274 280
3 449
239 241
75 239
42 239
280 425
375 486
8 280
95 388
321 342
39 280
95 487
219 449
188 312
188 417
270 424
92 375
264 280
59 280
188 444
79 399
188 418
320 424
156 3...

output:

10
188 424 63 399 280 239 95 449 375 342

result:

ok vertex cover of size 10

Test #26:

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

input:

500 1000
9 316
133 491
9 89
55 82
247 480
133 364
139 317
168 411
60 168
339 365
247 279
72 488
55 160
5 339
247 343
60 81
247 483
55 76
139 494
168 374
168 215
21 339
81 500
81 374
143 391
55 207
37 55
168 253
205 391
9 92
2 168
9 70
55 441
9 278
168 335
437 488
9 396
391 411
55 318
81 161
2 247
27...

output:

10
488 168 247 391 339 81 133 139 9 55

result:

ok vertex cover of size 10

Test #27:

score: 0
Accepted
time: 2ms
memory: 4156kb

input:

500 4000
34 440
276 370
287 292
23 449
23 400
34 179
44 317
23 115
30 34
276 388
88 129
276 415
165 300
123 249
300 445
122 287
276 431
283 484
30 283
23 169
276 460
170 270
164 283
123 397
23 263
129 175
208 287
300 315
170 292
66 170
287 375
126 276
287 441
287 487
88 287
300 418
262 276
44 206
11...

output:

10
123 44 287 300 170 23 129 34 276 283

result:

ok vertex cover of size 10

Test #28:

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

input:

500 500
12 25
334 479
235 352
343 496
120 445
178 477
93 477
124 364
55 294
222 463
29 191
18 107
38 97
142 451
29 78
237 438
98 196
26 234
16 189
15 311
297 339
107 300
176 442
218 222
8 396
335 336
456 474
276 495
130 350
59 498
18 441
303 376
308 357
10 35
114 470
403 476
234 282
132 372
6 37
179...

output:

188
1 2 3 4 37 8 9 116 11 66 13 92 15 16 17 239 19 20 22 23 70 25 26 27 28 29 30 31 32 178 34 35 36 38 293 41 42 43 44 45 46 47 348 332 52 424 54 294 56 57 59 390 441 291 377 217 65 196 71 420 213 419 75 237 77 79 234 81 113 86 87 257 93 94 436 381 97 100 157 324 103 421 105 107 139 109 154 112 470 ...

result:

ok vertex cover of size 188

Test #29:

score: 0
Accepted
time: 3ms
memory: 4132kb

input:

500 3000
27 174
78 179
309 321
33 313
219 225
203 316
30 149
266 270
106 350
369 463
74 433
54 398
82 296
276 430
291 419
122 412
343 427
76 163
113 398
147 482
113 263
56 411
383 396
115 149
161 276
130 207
163 297
191 283
2 68
25 419
120 414
133 409
308 321
235 476
89 176
46 130
80 113
293 405
52 ...

output:

200
1 68 466 4 311 203 319 470 90 46 414 12 490 14 310 16 327 216 19 20 183 121 23 467 25 190 27 28 285 30 132 32 364 488 228 36 37 499 197 412 72 42 129 378 208 403 48 263 50 51 382 53 398 184 56 57 58 380 200 62 63 315 331 141 207 199 283 71 73 482 495 76 77 78 461 80 468 368 322 229 329 87 274 46...

result:

ok vertex cover of size 200

Test #30:

score: 0
Accepted
time: 4ms
memory: 4132kb

input:

500 8000
94 339
209 235
86 449
123 181
230 282
69 341
199 324
21 194
7 72
36 379
75 234
73 84
233 379
148 377
32 56
5 264
111 453
246 475
32 96
202 433
235 328
49 298
104 346
349 427
243 484
104 380
10 477
303 318
57 90
84 347
65 442
188 212
318 323
283 404
127 463
26 490
58 160
430 456
21 147
5 35
...

output:

200
1 390 3 4 5 6 7 286 9 10 11 12 13 14 15 59 141 327 19 244 21 51 23 24 234 26 27 28 151 30 31 32 222 34 410 379 203 39 43 76 48 78 336 331 474 387 143 54 120 456 60 252 121 63 133 377 436 153 68 69 165 437 168 250 470 79 173 281 227 83 84 85 86 112 366 89 90 91 92 93 94 95 202 125 102 298 104 307...

result:

ok vertex cover of size 200

Test #31:

score: 0
Accepted
time: 8ms
memory: 4644kb

input:

500 20000
280 430
283 415
147 154
343 433
59 417
47 474
14 204
56 80
193 416
296 484
112 140
193 291
147 238
98 255
106 358
39 424
8 295
309 370
96 132
68 432
237 454
69 119
98 218
308 343
12 372
105 272
147 421
108 110
121 161
16 44
225 286
17 328
327 329
72 170
52 260
295 302
170 347
20 281
37 66
...

output:

200
1 338 352 4 317 92 207 108 66 10 67 12 87 339 15 301 410 263 19 62 365 289 23 163 390 86 27 261 391 225 31 98 494 34 266 36 144 181 39 256 270 42 484 44 459 46 47 48 204 142 51 52 285 140 408 101 337 58 72 380 219 295 403 65 299 321 490 71 464 133 367 78 208 80 94 308 83 407 85 406 89 90 303 230...

result:

ok vertex cover of size 200

Test #32:

score: 0
Accepted
time: 15ms
memory: 5112kb

input:

500 50000
103 130
189 432
290 497
46 337
113 237
249 333
162 376
181 272
30 101
58 192
252 362
374 424
85 322
201 432
163 340
74 99
69 424
189 416
160 343
235 425
70 304
50 322
21 370
38 338
395 469
141 468
146 471
282 497
249 265
131 292
6 417
239 326
243 347
155 167
130 209
17 302
189 222
100 291
...

output:

200
401 60 338 4 5 13 236 269 105 10 106 76 14 396 16 17 18 19 20 430 22 162 329 260 26 347 40 70 30 31 32 33 315 381 36 37 138 479 172 42 94 44 45 46 398 49 235 460 201 54 408 365 355 468 240 181 62 63 65 67 249 359 71 72 160 367 170 497 466 154 80 81 82 83 148 325 370 88 89 288 384 92 93 424 96 37...

result:

ok vertex cover of size 200

Test #33:

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

input:

10 20
8 9
1 4
7 9
9 10
3 4
2 4
2 9
4 9
2 7
6 9
2 6
4 10
2 3
1 2
5 9
4 6
4 5
2 8
4 8
2 5

output:

3
4 2 9

result:

ok vertex cover of size 3

Test #34:

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

input:

10 15
6 10
7 10
6 7
3 7
2 3
8 10
2 8
4 10
4 7
1 7
2 9
7 8
2 7
2 6
2 10

output:

3
7 2 10

result:

ok vertex cover of size 3

Test #35:

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

input:

10 33
1 4
1 3
4 6
3 10
1 9
6 7
4 10
3 8
4 5
8 10
7 9
3 7
4 8
6 8
2 4
4 7
9 10
2 7
2 5
2 8
7 10
2 10
1 6
8 9
5 10
6 10
2 3
2 9
1 8
1 10
3 4
7 8
1 2

output:

6
1 8 2 4 7 10

result:

ok vertex cover of size 6

Test #36:

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

input:

10 21
2 10
6 9
5 6
2 5
1 9
3 4
7 8
5 10
1 7
8 10
6 7
3 10
4 5
6 8
3 5
3 9
5 8
2 9
4 6
5 7
7 9

output:

6
9 5 3 6 7 10

result:

ok vertex cover of size 6

Test #37:

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

input:

100 70
8 82
29 50
29 54
65 97
42 43
4 65
42 84
8 16
17 42
62 65
40 82
12 65
65 99
29 86
29 41
56 65
8 58
32 42
63 85
42 64
65 71
45 65
63 95
22 29
63 87
16 29
24 29
34 42
42 50
46 82
78 82
10 42
52 82
29 94
42 89
42 82
39 82
29 45
42 91
39 63
42 70
29 81
8 51
61 65
8 47
72 82
65 98
31 63
82 98
42 60...

output:

6
65 8 42 29 63 82

result:

ok vertex cover of size 6

Test #38:

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

input:

100 222
77 94
75 77
40 87
36 53
21 46
46 56
46 75
31 74
43 77
41 77
67 77
77 81
4 100
55 86
47 77
65 71
58 75
49 94
27 78
32 36
46 94
4 77
42 77
7 71
40 72
1 27
37 93
22 40
50 77
46 74
77 92
86 93
27 59
77 80
36 70
53 100
4 73
77 98
32 55
53 93
34 100
66 93
62 93
72 77
73 77
69 71
40 88
36 57
52 94
...

output:

13
46 40 4 31 55 36 71 58 93 94 77 27 100

result:

ok vertex cover of size 13

Test #39:

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

input:

100 1000
22 84
10 46
40 91
10 49
29 89
6 18
5 7
49 76
73 83
42 56
67 82
26 31
49 50
55 100
26 52
68 80
26 61
40 43
39 46
72 99
4 91
6 67
4 61
25 99
54 65
58 99
46 68
51 93
54 94
33 85
16 84
45 75
76 84
25 61
50 84
31 71
26 69
61 100
86 100
10 51
31 82
50 66
47 69
24 69
66 99
7 75
21 31
39 51
69 79
3...

output:

30
6 40 89 65 76 7 61 85 10 13 56 46 69 78 18 52 91 31 92 100 82 83 50 99 45 84 51 94 57 68

result:

ok vertex cover of size 30

Test #40:

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

input:

100 1500
7 71
5 24
13 88
69 89
62 78
1 19
90 96
6 76
54 78
17 20
30 51
52 88
39 97
36 44
24 89
28 97
14 48
29 53
25 67
5 89
28 46
7 89
60 67
16 25
3 69
1 84
16 99
15 88
6 79
28 100
27 60
7 53
60 61
54 61
24 30
22 41
78 92
70 94
42 86
27 34
45 100
25 34
59 67
37 53
34 68
25 48
76 77
65 78
24 80
17 54...

output:

38
1 54 3 34 5 41 63 79 45 18 70 87 71 14 15 16 17 60 92 78 76 80 25 75 28 55 30 88 57 90 64 39 74 89 53 44 59 86

result:

ok vertex cover of size 38

Test #41:

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

input:

100 200
30 77
23 42
4 5
47 67
5 67
4 67
42 98
15 65
40 62
74 77
4 34
42 88
40 100
40 50
49 63
56 77
40 81
59 63
33 90
65 80
31 40
4 95
4 24
17 90
9 54
40 75
1 77
63 84
51 65
40 89
31 65
40 98
65 74
16 67
61 67
67 83
54 89
40 71
54 59
29 63
47 63
4 62
13 67
4 17
63 85
42 62
57 90
78 90
85 90
4 69
14 ...

output:

9
77 4 67 42 63 65 54 90 40

result:

ok vertex cover of size 9

Test #42:

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

input:

100 542
13 26
6 84
55 96
54 89
22 76
21 33
54 83
39 47
14 95
54 100
21 99
34 35
9 47
32 99
12 42
72 89
72 97
55 73
13 22
39 86
21 50
63 89
48 56
83 89
72 84
69 72
53 77
29 82
31 63
13 48
38 84
54 91
4 13
12 67
69 82
34 54
29 76
53 93
70 98
54 94
41 84
7 39
31 83
56 61
12 96
10 39
3 94
53 79
72 88
83...

output:

26
55 86 14 89 13 22 70 94 9 39 12 77 21 84 56 64 31 53 82 34 46 54 29 72 99 92

result:

ok vertex cover of size 26

Test #43:

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

input:

100 1320
55 58
21 34
3 51
14 38
1 70
8 89
79 97
19 57
60 86
35 64
10 50
73 76
12 66
18 32
95 100
65 71
12 44
26 100
15 50
26 38
1 58
12 41
75 86
23 42
2 44
35 90
70 88
15 66
18 59
28 87
32 78
17 54
43 53
56 66
40 96
5 75
34 97
6 59
62 66
9 85
2 38
23 75
12 80
86 95
4 42
3 66
17 71
68 73
50 89
30 84
...

output:

50
1 2 3 4 45 6 32 8 71 44 11 12 67 59 23 75 18 31 21 22 61 25 26 53 79 30 88 34 35 66 69 38 46 40 41 57 50 56 54 55 100 85 97 93 72 73 87 80 86 94

result:

ok vertex cover of size 50

Test #44:

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

input:

100 2530
81 86
11 29
75 96
10 24
57 92
47 73
67 96
4 61
23 99
3 84
1 18
78 96
20 23
4 97
1 73
45 74
12 43
33 100
8 43
1 86
40 77
33 58
21 95
7 28
23 46
77 88
25 33
14 60
8 85
24 48
37 90
54 60
59 78
51 85
14 73
48 79
8 41
19 87
58 81
56 60
56 81
26 44
21 32
33 85
64 85
42 85
64 96
41 91
8 96
43 94
4...

output:

44
1 41 3 4 20 37 7 8 85 10 11 68 60 15 18 95 39 23 24 43 78 28 96 30 31 32 33 90 92 55 62 87 44 45 47 79 51 52 80 73 81 61 77 76

result:

ok vertex cover of size 44

Test #45:

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

input:

500 700
163 469
134 331
95 134
72 185
46 185
131 163
163 263
185 398
185 343
188 265
134 260
134 176
76 185
134 273
163 389
185 218
265 398
185 323
134 315
112 163
185 393
163 441
185 273
134 174
163 323
108 265
163 299
134 333
92 134
198 265
75 265
265 277
163 492
134 436
265 413
134 181
185 309
9 ...

output:

4
185 265 134 163

result:

ok vertex cover of size 4

Test #46:

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

input:

500 2222
83 129
167 330
115 388
206 469
39 398
220 325
214 232
119 315
68 348
168 246
348 370
209 395
173 251
12 266
88 206
206 246
14 218
233 392
101 300
209 453
195 233
129 391
88 168
23 346
119 300
57 230
298 388
99 300
97 230
138 408
183 329
243 447
250 315
330 397
216 266
15 168
149 233
120 233...

output:

23
388 329 214 300 315 6 447 408 330 14 129 429 230 173 325 266 168 206 348 233 346 39 209

result:

ok vertex cover of size 23

Test #47:

score: 0
Accepted
time: 5ms
memory: 3964kb

input:

500 10000
188 494
326 448
330 493
239 259
89 130
173 383
250 445
181 380
176 395
112 320
52 228
30 317
383 392
52 212
238 363
92 490
192 208
91 188
88 363
97 419
131 141
186 500
289 411
3 50
240 443
26 112
70 238
55 178
56 94
37 231
119 174
52 402
210 258
131 349
65 493
11 390
12 418
43 397
11 498
2...

output:

100
274 330 3 357 5 392 174 326 297 10 11 12 490 14 336 185 317 444 311 412 55 283 104 488 220 434 373 229 323 450 335 407 359 43 310 131 59 186 41 91 248 45 269 319 262 175 464 181 52 383 374 56 85 58 193 411 406 419 360 422 435 497 182 334 445 292 443 258 122 493 238 119 130 259 228 352 231 88 140...

result:

ok vertex cover of size 100

Test #48:

score: 0
Accepted
time: 14ms
memory: 5708kb

input:

500 89505
63 230
260 427
211 269
185 348
394 402
142 308
48 186
123 257
7 496
74 227
97 274
156 175
212 279
174 329
10 293
56 221
11 187
48 70
19 203
128 305
22 179
183 402
457 493
89 233
174 472
1 457
258 338
180 305
5 79
125 227
79 499
350 353
140 162
81 451
64 387
284 376
24 182
299 327
66 396
71...

output:

234
149 2 3 4 5 6 7 8 9 140 11 314 13 144 39 472 277 89 19 227 21 23 90 280 26 40 230 30 106 357 66 34 414 390 67 38 468 42 402 499 45 72 47 48 452 50 51 145 330 427 55 56 57 109 114 451 283 64 182 308 126 104 71 129 418 426 77 404 79 80 382 82 194 216 86 87 88 422 101 298 95 96 490 98 326 155 102 4...

result:

ok vertex cover of size 234

Test #49:

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

input:

500 900
7 417
97 388
305 372
102 220
62 351
161 264
191 239
84 244
391 460
245 358
89 303
129 138
64 355
121 200
197 325
35 436
131 375
74 148
171 305
191 388
84 151
329 492
16 444
16 347
24 324
92 376
248 388
231 398
189 409
320 392
301 485
422 490
275 500
36 454
41 221
252 490
162 215
35 445
214 3...

output:

181
1 2 3 4 357 6 7 8 9 10 167 12 168 190 222 16 472 240 474 187 21 41 292 95 312 346 58 265 30 302 414 255 35 36 37 440 39 40 263 141 335 194 291 467 352 129 89 247 146 54 55 56 325 282 60 61 62 277 64 207 66 154 68 69 395 200 304 148 75 371 78 308 324 311 287 84 85 433 165 392 117 206 92 94 96 97 ...

result:

ok vertex cover of size 181

Test #50:

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

input:

500 3222
459 494
86 232
124 377
147 320
195 230
479 496
58 364
290 324
195 389
19 424
5 324
134 309
88 489
99 489
195 497
98 109
387 489
140 239
119 150
70 424
309 355
34 195
489 497
29 425
98 463
455 496
310 489
98 316
214 309
437 496
359 494
119 253
361 377
13 364
22 51
377 404
424 455
310 494
316...

output:

17
22 250 489 147 494 86 239 324 377 119 496 364 195 424 309 98 425

result:

ok vertex cover of size 17

Test #51:

score: 0
Accepted
time: 5ms
memory: 4028kb

input:

500 9900
68 260
76 109
427 464
109 464
364 436
259 427
138 371
108 477
52 148
38 363
172 422
142 197
392 425
15 339
99 226
99 228
25 118
81 336
15 72
252 336
265 480
73 498
113 337
418 468
169 272
380 494
273 336
45 69
189 290
9 95
155 159
45 64
95 227
345 446
48 494
148 151
93 439
192 354
13 267
26...

output:

91
84 135 290 484 213 267 430 159 109 236 265 240 456 380 15 226 416 75 244 471 22 23 278 25 72 34 327 29 367 496 157 176 260 248 357 363 435 95 257 100 44 45 93 345 138 379 124 165 185 425 194 66 57 494 142 73 477 223 158 64 86 67 458 468 301 427 113 148 234 127 410 91 336 192 334 381 479 489 495 4...

result:

ok vertex cover of size 91

Test #52:

score: 0
Accepted
time: 22ms
memory: 6208kb

input:

500 86247
121 224
151 297
213 289
12 408
112 284
128 369
234 499
195 396
268 305
158 500
247 299
358 403
330 375
71 212
78 477
12 463
220 457
322 384
191 286
111 437
223 495
419 464
2 447
292 303
149 474
250 326
108 150
61 346
292 333
121 258
223 231
81 90
150 389
178 266
127 331
14 346
28 291
432 4...

output:

222
240 2 28 212 5 6 111 224 9 234 12 44 14 15 289 17 478 140 414 86 431 304 25 26 421 359 30 31 151 194 34 191 36 70 417 39 40 58 354 114 351 47 110 49 455 51 65 53 55 56 339 213 133 199 456 64 66 95 487 69 393 299 157 74 75 230 435 78 79 80 81 82 454 84 85 226 89 476 108 92 93 484 97 178 243 279 2...

result:

ok vertex cover of size 222

Test #53:

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

input:

7 15
3 6
1 2
5 6
2 6
2 7
1 5
3 5
1 3
2 5
3 4
3 7
2 4
4 7
5 7
1 4

output:

4
3 2 4 5

result:

ok vertex cover of size 4

Test #54:

score: -100
Wrong Answer
time: 0ms
memory: 3912kb

input:

7 16
5 6
1 2
2 3
3 4
2 7
3 5
2 6
2 4
3 7
1 4
4 5
4 6
1 5
1 7
6 7
5 7

output:

not smol

result:

wrong answer vertex cover is smol, but participant did not print it
English 繁體中文 简体中文

Server Time: 2024-12-04 19:23:30 | OpenSource Project