QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #421432 | #961. Smol Vertex Cover | cqbzly | WA | 695ms | 6552kb | C++20 | 3.7kb | 2024-05-25 18:39:52 | 2024-05-25 18:39:53 |
Judging History
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(0714);
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 k=1;k<=10;k++){
for(int i=n;i>=1;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;
}
}
// cout<<cnt<<"\n";
// for(int i=1;i<=cnt;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<=n;i++){
init();
if(to[i]){
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;
}
}
else{
for(int j=1;j<=m;j++){
int u=a[j].fi,v=a[j].se;
if(u==i||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";
cout<<i<<" ";
for(int j=1;j<=cnt;j++){
if(fk[j]<fk[j+cnt])cout<<p[j].fi<<" ";
else cout<<p[j].se<<" ";
}
cout<<"\n";
break;
}
}
}
if(!flg)cout<<"not smol"<<"\n";
}
// }
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3576kb
input:
5 5 1 2 2 3 3 4 4 5 1 5
output:
3 1 2 4
result:
ok vertex cover of size 3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3844kb
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: 0ms
memory: 3672kb
input:
3 0
output:
0
result:
ok vertex cover of size 0
Test #4:
score: 0
Accepted
time: 1ms
memory: 3572kb
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: 1ms
memory: 3680kb
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 2 6 10 8 7
result:
ok vertex cover of size 6
Test #6:
score: 0
Accepted
time: 1ms
memory: 3624kb
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: 3632kb
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: 0ms
memory: 3768kb
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: 3644kb
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: 3ms
memory: 3684kb
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: 12ms
memory: 4072kb
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: 3652kb
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 12 399 17 18 20 21 22 24 30 32 34 39 109 43 44 45 46 86 49 50 52 94 54 55 394 481 60 64 67 68 73 76 78 208 294 82 85 410 91 92 95 351 99 101 107 110 113 115 116 118 120 121 122 127 128 470 140 146 149 260 151 152 421 158 159 160 163 173 176 177 179 202 181 182 183 185 187 188 189 196 1...
result:
ok vertex cover of size 147
Test #13:
score: 0
Accepted
time: 8ms
memory: 3708kb
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: 29ms
memory: 3904kb
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: 695ms
memory: 6552kb
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: 3684kb
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 14 7 19 10 12 18
result:
ok vertex cover of size 9
Test #17:
score: 0
Accepted
time: 1ms
memory: 3688kb
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 12 3 13 9 16 7 8 10 18
result:
ok vertex cover of size 10
Test #18:
score: 0
Accepted
time: 0ms
memory: 3624kb
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 11 8 6 7 10 12 13 18
result:
ok vertex cover of size 10
Test #19:
score: 0
Accepted
time: 0ms
memory: 3928kb
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 9 24 47 48 54 57 100 107 110 103
result:
ok vertex cover of size 10
Test #20:
score: 0
Accepted
time: 1ms
memory: 3804kb
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 8 10 15 18 21 43 51 53 69 81
result:
ok vertex cover of size 10
Test #21:
score: 0
Accepted
time: 0ms
memory: 3712kb
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 42 25 34 87 106 95 96 102 109
result:
ok vertex cover of size 10
Test #22:
score: 0
Accepted
time: 1ms
memory: 3948kb
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 164 3 4 5 178 7 191 188 10 127 12 93 37 15 72 132 100 116 20 81 119 61 24 25 26 41 167 89 32 142 49 46 122 38 39 73 42 43 44 45 47 67 78 51 52 158 55 118 105 124 121 62 63 64 65 170 109 117 135 125 163 189 123 137 84 86 87 88 90 91 145 139 197 156 174 195 104 106 173 155 130 111 112 171 157 15...
result:
ok vertex cover of size 100
Test #23:
score: 0
Accepted
time: 1ms
memory: 3756kb
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 190 3 4 157 197 184 8 103 101 11 12 193 113 170 16 29 27 19 142 187 83 23 24 25 26 28 30 31 60 192 174 35 36 164 78 73 165 43 61 45 46 179 48 49 51 53 172 55 108 57 58 147 62 64 86 135 169 89 70 71 111 75 159 186 80 82 128 85 87 88 115 91 104 114 161 112 153 143 105 116 118 119 171 154 141 138...
result:
ok vertex cover of size 100
Test #24:
score: 0
Accepted
time: 2ms
memory: 4036kb
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 190 111 5 30 7 89 140 10 11 189 80 169 126 16 54 163 19 20 21 108 24 135 152 79 28 29 31 32 91 38 195 36 37 164 83 41 42 181 161 139 46 118 177 199 183 52 123 98 57 58 59 60 61 62 109 129 65 194 67 85 69 159 112 72 73 148 75 81 105 182 86 171 137 133 141 162 100 115 104 167 110 116 117 119 1...
result:
ok vertex cover of size 100
Test #25:
score: 0
Accepted
time: 1ms
memory: 3652kb
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 63 95 188 239 280 342 375 399 424 449
result:
ok vertex cover of size 10
Test #26:
score: 0
Accepted
time: 2ms
memory: 3932kb
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 9 55 81 133 139 168 247 339 391 488
result:
ok vertex cover of size 10
Test #27:
score: 0
Accepted
time: 4ms
memory: 3840kb
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 23 34 44 123 129 170 276 283 287 300
result:
ok vertex cover of size 10
Test #28:
score: 0
Accepted
time: 1ms
memory: 3764kb
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 8 9 116 11 13 15 16 17 19 20 22 23 24 25 26 27 28 29 30 31 32 34 35 36 37 38 41 42 43 44 45 46 47 52 231 54 56 57 59 441 65 66 196 71 294 75 77 79 234 81 86 87 92 93 94 213 381 97 100 324 103 421 105 107 109 154 112 113 470 434 291 424 120 122 386 124 330 129 130 372 385 136 249 139 359 ...
result:
ok vertex cover of size 188
Test #29:
score: 0
Accepted
time: 17ms
memory: 3772kb
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 4 197 12 490 14 16 199 19 20 311 23 25 27 28 30 32 121 36 37 42 72 253 46 48 274 50 51 115 53 56 57 58 343 62 63 68 208 71 73 76 77 78 80 469 87 449 176 90 92 211 428 477 106 107 319 168 112 123 124 125 127 128 129 256 131 132 133 461 139 141 143 145 146 148 154 224 159 161 162 172 196 200 181...
result:
ok vertex cover of size 200
Test #30:
score: 0
Accepted
time: 29ms
memory: 4204kb
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 3 4 5 6 7 9 10 11 12 13 14 15 19 377 21 23 24 92 26 27 28 30 31 32 376 34 224 39 43 48 338 51 54 489 215 59 60 63 153 68 69 76 409 78 79 83 84 85 86 493 89 90 91 93 94 95 408 102 104 426 106 107 110 112 113 115 118 119 120 121 123 255 125 127 128 129 133 239 135 136 139 140 141 143 144 146 149...
result:
ok vertex cover of size 200
Test #31:
score: 0
Accepted
time: 60ms
memory: 4348kb
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 240 4 465 203 10 337 12 433 113 15 19 23 321 482 27 31 476 34 36 39 42 44 338 46 47 48 459 51 52 346 58 256 62 270 455 65 66 67 417 288 71 72 78 80 83 85 86 87 89 90 403 92 94 295 98 101 104 115 106 108 109 246 114 117 119 121 319 123 442 125 251 131 132 133 136 139 140 142 144 447 310 147 441...
result:
ok vertex cover of size 200
Test #32:
score: 0
Accepted
time: 136ms
memory: 5108kb
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 99 4 5 10 116 13 14 16 17 18 19 20 22 26 30 31 32 33 36 37 240 40 454 42 44 45 46 412 151 49 76 126 54 88 138 60 62 63 65 67 70 71 72 359 466 370 80 81 82 83 89 92 93 94 96 352 107 100 105 106 109 163 113 115 120 121 124 162 129 130 132 160 140 142 356 169 145 146 148 255 154 156 159 165 314 167...
result:
ok vertex cover of size 200
Test #33:
score: 0
Accepted
time: 0ms
memory: 3616kb
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 2 4 9
result:
ok vertex cover of size 3
Test #34:
score: 0
Accepted
time: 0ms
memory: 3624kb
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 2 7 10
result:
ok vertex cover of size 3
Test #35:
score: 0
Accepted
time: 0ms
memory: 3576kb
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 2 4 10 7 8
result:
ok vertex cover of size 6
Test #36:
score: 0
Accepted
time: 0ms
memory: 3616kb
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 7 10 4 5 8 9
result:
ok vertex cover of size 6
Test #37:
score: 0
Accepted
time: 0ms
memory: 3704kb
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 8 29 42 63 65 82
result:
ok vertex cover of size 6
Test #38:
score: 0
Accepted
time: 1ms
memory: 3936kb
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 4 27 31 36 40 46 55 58 100 71 77 94 93
result:
ok vertex cover of size 13
Test #39:
score: 0
Accepted
time: 2ms
memory: 3732kb
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 40 6 7 10 13 57 18 69 31 84 45 46 50 51 52 92 56 76 61 65 68 100 85 78 99 82 83 89 91 94
result:
ok vertex cover of size 30
Test #40:
score: 0
Accepted
time: 2ms
memory: 3676kb
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 3 5 14 15 16 17 18 59 90 25 28 30 34 39 41 64 44 45 71 75 57 74 92 60 53 54 55 87 86 63 70 76 78 79 80 88 89
result:
ok vertex cover of size 38
Test #41:
score: 0
Accepted
time: 1ms
memory: 3804kb
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 4 40 42 54 63 65 67 77 90
result:
ok vertex cover of size 9
Test #42:
score: 0
Accepted
time: 2ms
memory: 3644kb
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 94 9 12 13 14 21 22 29 31 34 77 39 46 53 54 55 56 64 72 70 89 92 82 84 86 99
result:
ok vertex cover of size 26
Test #43:
score: 0
Accepted
time: 1ms
memory: 3684kb
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 56 8 85 22 11 12 18 30 80 75 97 21 23 44 25 26 71 73 88 31 32 53 34 35 94 38 40 41 69 46 59 50 93 54 55 57 79 61 87 66 67 72 86 100
result:
ok vertex cover of size 50
Test #44:
score: 0
Accepted
time: 2ms
memory: 3956kb
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 3 4 32 7 8 10 11 95 15 39 18 20 44 23 24 68 81 28 30 31 33 55 37 41 52 43 45 47 78 51 80 96 90 60 61 62 73 85 87 76 77 79 92
result:
ok vertex cover of size 44
Test #45:
score: 0
Accepted
time: 0ms
memory: 3956kb
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 134 163 185 265
result:
ok vertex cover of size 4
Test #46:
score: 0
Accepted
time: 6ms
memory: 3760kb
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 6 14 39 129 168 173 206 209 214 230 233 266 300 315 325 329 330 346 348 388 408 429 447
result:
ok vertex cover of size 23
Test #47:
score: 0
Accepted
time: 38ms
memory: 3860kb
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 3 5 10 11 12 14 58 41 43 45 52 55 56 59 419 85 88 91 104 112 119 122 130 131 133 181 140 156 274 174 175 182 185 186 188 192 193 210 383 220 228 229 231 238 248 258 259 261 262 263 269 273 275 283 292 297 305 310 311 317 319 323 326 330 334 335 336 348 350 351 352 357 359 360 370 371 373 374 474...
result:
ok vertex cover of size 100
Test #48:
score: 0
Accepted
time: 80ms
memory: 5624kb
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 155 2 3 4 5 6 7 8 9 11 13 218 45 241 19 432 21 217 23 329 26 233 365 149 30 34 38 39 40 72 42 214 47 48 108 50 51 210 55 56 57 348 484 64 66 67 111 71 485 77 79 80 82 86 87 88 89 90 421 161 95 96 457 98 101 102 110 104 106 107 109 112 114 246 120 451 123 126 442 207 129 132 134 135 136 200 138 2...
result:
ok vertex cover of size 234
Test #49:
score: 0
Accepted
time: 4ms
memory: 3748kb
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 6 7 8 9 10 12 272 16 17 21 403 282 209 30 302 414 445 36 37 39 40 41 263 194 395 54 55 56 58 60 61 62 277 64 66 68 69 75 78 156 84 85 448 89 92 94 95 96 97 99 102 283 306 113 115 117 119 129 375 133 134 136 138 141 143 354 471 146 148 326 428 154 440 287 317 215 163 164 165 167 168 170 1...
result:
ok vertex cover of size 181
Test #50:
score: 0
Accepted
time: 6ms
memory: 4036kb
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 86 98 119 147 195 239 250 489 309 324 364 377 424 425 496 494
result:
ok vertex cover of size 17
Test #51:
score: 0
Accepted
time: 37ms
memory: 3972kb
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 15 22 23 25 29 34 44 45 272 380 57 427 116 64 66 67 72 73 75 84 86 91 93 95 99 100 109 113 124 127 135 138 142 148 495 157 158 159 165 244 176 178 236 185 311 192 194 213 217 223 226 233 234 240 248 257 260 265 267 278 290 295 301 327 334 336 345 354 357 363 367 379 381 496 471 425 410 416 456 48...
result:
ok vertex cover of size 91
Test #52:
score: 0
Accepted
time: 116ms
memory: 5920kb
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 2 5 6 476 379 9 12 14 15 445 17 66 25 26 499 28 30 31 34 36 39 40 93 44 306 47 110 49 251 51 53 55 56 58 120 133 64 65 69 70 74 75 308 78 79 80 81 82 84 85 86 89 417 92 473 95 97 102 421 105 492 108 109 111 112 114 117 408 122 121 123 124 125 126 128 134 135 484 335 139 140 441 146 213 149 151 1...
result:
ok vertex cover of size 222
Test #53:
score: -100
Wrong Answer
time: 0ms
memory: 3848kb
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:
not smol
result:
wrong answer vertex cover is smol, but participant did not print it