QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #654134 | #4829. Mark on a Graph | rotcar07 | 0 | 2ms | 4824kb | C++23 | 792b | 2024-10-18 21:08:28 | 2024-10-18 21:08:32 |
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int N=1005;
int n,m,deg[N];bool g[N][N];
int main(){
cin>>n>>m;int up=m/n;
for(int i=1,u,v;i<=m;i++) cin>>u>>v,g[v][u]=g[u][v]=1,deg[u]++,deg[v]++;
bool win=0;
for(int i=1;i<=n&&!win;i++)if(deg[i]<=up+5){
int cnt=0;
for(int j=1;j<=n;j++) if(g[i][j]&°[j]<=up+1) cnt++;
if(cnt>=5) win=1;
}
if(win) return puts("ok"),0;
puts("mark");
for(int i=1;i<=n;i++)if(deg[i]<=up){
int cnt=5;
vector<pair<int,int>> v;
for(int j=i+1;j<=n&&cnt;j++) if(deg[j]<=up){
cnt--;
if(!g[i][j]) v.emplace_back(i,j);
}
cout<<v.size()<<'\n';
for(auto [x,y]:v) cout<<x<<' '<<y<<'\n';
return 0;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 4616kb
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 32 40 32 65 32 73 32 90 32 106
input:
1000 3565 721 353 606 33 429 542 522 656 682 141 194 833 746 181 165 850 263 583 392 102 221 187 643 633 788 161 180 790 481 180 640 763 583 378 224 873 974 302 521 639 368 691 720 39 113 433 679 583 16 526 882 125 351 806 509 955 464 840 322 379 161 916 232 79 178 201 182 394 201 34 883 528 916 901...
output:
ok
result:
ok all right
Test #2:
score: 100
Accepted
time: 2ms
memory: 4824kb
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 4 6 4 9 4 10 4 13 4 15
input:
1000 2005 674 235 170 611 339 156 250 778 470 422 361 300 610 274 440 112 90 337 81 879 505 764 37 6 935 217 424 667 914 38 740 19 121 843 87 330 441 646 764 431 882 331 763 804 318 988 904 500 999 663 53 985 978 756 246 228 131 622 58 21 528 824 411 674 835 561 569 980 502 456 164 502 633 94 303 24...
output:
ok
result:
ok all right
Test #3:
score: 100
Accepted
time: 2ms
memory: 4600kb
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 8 10 8 21 8 68 8 80 8 87
input:
1000 5005 551 153 334 992 476 219 208 346 392 91 425 127 150 361 273 972 141 573 341 805 699 578 106 119 985 570 128 182 593 923 647 685 128 752 345 596 992 354 384 526 309 736 890 582 471 552 890 461 326 688 305 830 809 203 138 888 321 569 836 399 207 306 5 115 344 235 781 688 560 544 129 462 530 8...
output:
ok
result:
ok all right
Test #4:
score: 100
Accepted
time: 2ms
memory: 4576kb
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 5 7 14 7 46 7 52 7 58 7 104
input:
1000 3161 378 209 409 35 856 354 70 275 706 752 786 22 612 817 712 156 926 271 606 440 919 879 761 982 111 489 856 566 668 1 835 827 7 717 57 286 481 64 166 575 912 865 182 574 853 843 669 210 697 40 840 516 403 962 295 679 245 501 747 434 984 310 827 597 325 695 127 255 643 111 136 517 94 882 59 27...
output:
ok
result:
ok all right
Test #5:
score: 100
Accepted
time: 2ms
memory: 4804kb
input:
1000 3433 634 21 789 966 541 959 213 381 366 781 107 649 747 122 336 869 222 648 833 972 929 524 712 524 744 525 568 679 634 163 901 501 56 518 128 587 720 117 208 439 860 85 852 168 934 947 34 858 520 568 408 464 232 432 999 504 71 982 957 372 570 436 281 309 410 405 521 275 554 589 4 707 498 148 5...
output:
mark 5 1 4 1 45 1 66 1 104 1 121
input:
1000 3438 588 522 191 554 344 682 96 559 647 120 522 106 18 372 644 165 989 968 563 502 266 521 845 45 607 952 917 666 567 382 983 160 227 300 799 194 810 211 800 435 774 369 40 776 182 66 35 931 701 539 188 541 784 754 311 347 131 959 182 222 86 971 802 441 697 539 788 38 82 305 268 966 866 909 745...
output:
ok
result:
ok all right
Test #6:
score: 0
Wrong Answer on the first run
input:
1000 3057 985 223 432 967 405 822 845 650 893 646 599 718 754 710 333 73 392 355 895 496 200 562 816 36 457 953 9 623 889 662 482 590 249 29 689 694 185 990 285 690 12 323 611 560 903 722 476 86 105 666 441 193 695 640 36 617 840 42 80 527 977 539 606 150 384 585 784 648 919 360 157 532 568 98 995 8...
output:
ok
input:
output:
result:
wrong answer Token "ok" doesn't correspond to pattern "mark"