QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #312399 | #4829. Mark on a Graph | trsins | 0 | 2ms | 24420kb | C++14 | 708b | 2024-01-23 21:08:32 | 2024-01-23 21:08:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+4;
int n,m,g[N][N],deg[N],a[N],p[N];
vector<pair<int,int>>e;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
g[u][v]=g[v][u]=1,deg[u]++,deg[v]++;
}
for(int i=1;i<=n;i++)p[i]=i;
sort(p+1,p+n+1,[&](int u,int v){return deg[u]>deg[v];});
sort(p+1,p+5+1);for(int i=1;i<=5;i++)a[i]=i;
int _=120;while(_--){e.clear();
for(int i=1;i<=5;i++)if(!g[p[a[i]]][p[a[i%5+1]]])e.push_back(make_pair(p[a[i]],p[a[i]%5+1]));
if(!e.size())return puts("ok"),0;
next_permutation(a+1,a+5+1);
}printf("mark %d\n",e.size());
for(auto t:e)printf("%d %d\n",t.first,t.second);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 24420kb
input:
1000 3560 603 151 415 20 102 569 895 552 678 734 24 614 689 518 440 223 751 919 223 433 711 551 502 634 706 583 812 501 514 535 780 751 720 530 532 384 888 139 864 791 292 675 171 881 30 592 464 557 280 299 654 650 894 335 250 532 792 10 83 969 118 771 579 300 852 983 243 940 957 939 817 889 911 319...
output:
mark 5 733 139 494 733 310 494 252 310 139 252
input:
1000 3565 721 353 295 222 429 542 534 977 682 141 495 833 746 181 656 183 184 255 392 102 439 187 643 633 448 161 180 790 655 180 484 763 439 897 224 873 974 302 521 734 368 691 794 364 113 49 66 583 16 526 457 125 567 806 70 757 464 840 11 36 161 397 232 412 178 201 182 394 201 34 992 583 65 485 25...
output:
ok
result:
ok all right
Test #2:
score: 100
Accepted
time: 0ms
memory: 22912kb
input:
1000 2000 457 335 160 497 464 992 892 255 853 3 308 301 970 363 541 299 89 418 425 128 626 827 603 854 484 874 755 295 607 483 798 552 356 850 320 357 254 940 675 901 168 525 301 636 520 555 773 910 343 701 889 966 218 529 909 950 71 64 682 284 424 138 721 792 670 544 386 72 654 909 725 235 592 437 ...
output:
mark 5 902 79 761 902 747 761 727 747 79 727
input:
1000 2005 711 181 320 426 386 503 377 826 97 233 792 231 1 993 440 112 532 381 784 940 505 764 73 6 935 217 640 649 546 673 751 756 178 529 731 827 689 39 764 431 683 73 835 379 727 755 904 500 999 257 70 274 564 74 863 90 543 99 741 982 450 635 411 674 705 758 507 167 414 78 164 502 633 94 50 924 5...
output:
ok
result:
ok all right
Test #3:
score: 100
Accepted
time: 2ms
memory: 22876kb
input:
1000 5000 449 632 597 26 701 322 249 190 411 770 666 596 989 995 112 861 445 818 544 659 24 680 739 593 344 439 193 932 600 526 574 869 216 918 716 793 259 686 555 993 255 578 659 271 328 524 729 672 39 771 241 866 27 790 417 109 56 403 338 299 387 232 280 306 589 794 833 419 900 802 54 697 539 807 ...
output:
mark 5 869 539 748 869 593 748 566 593 539 566
input:
1000 5005 551 153 421 786 276 219 208 346 802 385 305 127 150 361 435 479 24 121 206 805 699 578 106 119 963 570 128 182 917 352 647 41 128 752 345 908 992 449 13 996 854 165 890 582 471 359 669 461 326 618 127 830 62 839 138 888 321 569 57 143 207 306 5 115 344 898 781 131 629 274 129 462 530 634 8...
output:
ok
result:
ok all right
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 22956kb
input:
1000 3156 347 398 792 278 754 442 413 757 391 130 636 625 207 437 81 415 47 974 887 779 524 619 379 894 868 594 653 919 29 117 123 867 632 505 648 147 130 420 495 876 637 659 882 348 462 878 282 646 398 525 419 224 926 448 305 934 855 570 396 345 774 918 336 123 502 491 984 783 845 142 790 594 754 4...
output:
mark 4 598 115 422 598 418 422 222 418
input:
1000 3158 540 943 439 852 904 654 845 121 154 753 213 734 215 276 159 469 266 325 123 439 16 909 157 346 810 843 150 447 394 426 811 101 642 355 492 105 437 788 885 38 865 396 418 309 397 703 287 297 786 474 456 465 441 28 766 878 918 911 74 668 310 817 34 879 394 334 639 127 836 887 748 615 334 741...
output:
mark 5 994 177 741 994 597 741 247 597 177 247
result:
wrong answer Token "mark" doesn't correspond to pattern "ok"