QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #115254 | #5029. 在路上 | lgvc# | 20 | 2978ms | 475200kb | C++23 | 1.2kb | 2023-06-25 13:18:31 | 2024-05-31 14:11:10 |
Judging History
answer
#include "path.h"
#include <bits/stdc++.h>
std::unordered_map<int,int> vv[50009];
int siz[50009],vq[50009],vt[50009];
void as(int n,int N) {
if(vt[n]) return;
vt[n]=1;siz[n]=1;
for(int i=1;i<=N;i++) {
if(i==n) continue;
vv[n][i]=ask(1,n,i);
if(vv[n][i]==n) siz[n]++;
}
vv[n][n]=n;
}
int centroid(int id,int N,int M) {
int c=1;
memset(vt,0,sizeof(vt));
for(int i=1;i<=N;i++) vv[i].clear();
for(int i=1;i<=N;i++) {
vv[1][i]=1;
}
vt[1]=1;
siz[1]=N;
int cq=8;
while(cq--) {
int x=rand()%N+1;
while(vv[c][x]!=c||x==c) {
x=rand()%N+1;
}
memset(vq,0,sizeof(vq));
vq[x]=1;
for(int i=1;i<=N;i++) {
if(i!=x&&i!=c&&ask(x,c,i)==i) vq[i]=1;
}
while(1) {
int at=0;
for(int i=1;i<=N;i++) if(vq[i]) at++;
if(at==0) break;
int md=rand()%at+1,ct=0;
for(int i=1;i<=N;i++) if(vq[i]) {
ct++;
if(ct==md) {
md=i;
break;
}
}
as(md,N);
if(siz[md]>N/2) {
for(int i=1;i<=N;i++) {
if(vq[i]) {
if(vv[md][i]==i) vq[i]=0;
}
}
c=md;
} else {
for(int i=1;i<=N;i++) {
if(vq[i]) {
if(vv[md][i]==md) vq[i]=0;
}
}
}
}
}
return c;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 14124kb
input:
1 100 100 3 1 2 3 1 2 3 3 1 3 1 2 3 1 2 3 3 1 3 1 2 3 3 1 3 1 2 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 1 2 3 1 2 3 3 1 3 3 1 3 1 2 3 3 1 3 3 1 3 1 2 3 3 1 3 3 1 3 1 2 3 3 1 3 3 1 3 3 1 3 1 2 3 1 2 3 3 1 3 3 1 3 1 2 3 1 2 3 1 2 3 1 2 3 3 1 3 3 1 3 3 1 3 1 2 3 1 2 3 1 2 3 3 1 3 3 1 3 3 1 3 ...
result:
wrong answer too many queries
Subtask #2:
score: 8
Accepted
Test #2:
score: 8
Accepted
time: 23ms
memory: 22720kb
input:
2 10 10000000 999 60 112 98 509 586 175 588 875 861 516 920 370 781 249 999 649 292 308 934 949 437 92 506 752 547 866 869 510 984 228 104 612 202 630 360 809 56 107 566 448 940 726 146 299 941 50 319 794 670 603 365 492 728 872 829 942 451 632 373 106 909 25 306 995 735 99 568 673 75 573 383 407 56...
result:
ok correct
Test #3:
score: 0
Accepted
time: 27ms
memory: 20276kb
input:
2 10 10000000 999 60 112 98 509 586 175 588 875 861 516 920 370 781 249 999 649 292 308 934 949 437 92 506 752 547 866 869 510 984 228 104 612 202 630 360 809 56 107 566 448 940 726 146 299 941 50 319 794 670 603 365 492 728 872 829 942 451 632 373 106 909 25 306 995 735 99 568 673 75 573 383 407 56...
result:
ok correct
Test #4:
score: 0
Accepted
time: 24ms
memory: 19596kb
input:
2 10 10000000 999 60 112 959 68 586 835 91 836 634 516 272 912 781 249 655 11 466 103 934 816 904 92 576 83 687 435 871 510 758 519 842 882 339 221 2 917 5 605 477 448 323 723 744 494 941 50 668 751 670 336 365 95 877 159 829 957 451 632 591 616 909 83 452 607 735 99 22 570 755 354 172 711 742 870 3...
result:
ok correct
Test #5:
score: 0
Accepted
time: 24ms
memory: 20836kb
input:
2 10 10000000 999 373 769 355 568 586 175 588 836 203 901 272 948 781 80 655 11 292 103 934 595 904 188 865 989 698 493 871 510 893 228 842 882 339 630 2 550 829 107 477 636 385 726 146 299 764 670 668 381 631 336 365 95 974 872 829 733 678 669 373 571 183 752 452 607 735 179 22 673 755 354 383 711 ...
result:
ok correct
Test #6:
score: 0
Accepted
time: 10ms
memory: 18920kb
input:
2 10 10000000 999 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 68...
result:
ok correct
Test #7:
score: 0
Accepted
time: 3ms
memory: 18916kb
input:
2 10 10000000 999 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 688 68...
result:
ok correct
Test #8:
score: 0
Accepted
time: 23ms
memory: 22668kb
input:
2 10 10000000 999 158 826 595 867 47 385 664 154 455 857 622 561 166 780 801 763 33 310 605 36 199 718 762 911 419 109 947 369 861 841 902 657 172 175 461 814 473 43 90 875 62 238 669 791 68 435 405 663 756 255 628 798 745 878 257 773 652 662 832 735 75 363 129 359 230 351 667 873 602 783 988 253 58...
result:
ok correct
Test #9:
score: 0
Accepted
time: 29ms
memory: 22824kb
input:
2 10 10000000 999 279 772 39 665 622 173 514 309 407 623 288 342 100 529 202 417 132 611 186 430 634 796 454 842 92 53 977 712 975 158 654 66 822 452 6 333 596 593 91 119 242 503 190 82 97 575 663 574 75 598 299 334 31 147 382 988 702 11 801 338 164 696 573 182 899 948 507 168 331 939 442 137 581 52...
result:
ok correct
Test #10:
score: 0
Accepted
time: 12ms
memory: 17532kb
input:
2 10 10000000 999 60 208 208 208 208 175 208 875 861 208 208 370 208 208 208 208 292 208 208 949 208 208 208 752 547 208 869 510 208 208 208 612 208 208 360 809 208 107 208 448 208 208 208 208 941 208 319 794 208 603 208 208 208 208 208 208 451 208 373 106 208 25 306 208 735 99 208 673 208 573 383 2...
result:
ok correct
Test #11:
score: 0
Accepted
time: 12ms
memory: 20980kb
input:
2 10 10000000 999 60 208 208 208 208 175 208 875 861 208 208 370 208 208 208 208 292 208 208 949 208 208 208 752 547 208 869 510 208 208 208 612 208 208 360 809 208 107 208 448 208 208 208 208 941 208 319 794 208 603 208 208 208 208 208 208 451 208 373 106 208 25 306 208 735 99 208 673 208 573 383 2...
result:
ok correct
Test #12:
score: 0
Accepted
time: 11ms
memory: 18608kb
input:
2 10 10000000 999 198 236 761 86 644 189 7 741 274 656 547 36 825 827 740 333 896 832 575 37 359 456 833 590 427 837 100 60 424 237 208 742 266 543 941 906 422 423 953 787 397 337 215 469 979 51 404 546 603 168 849 472 737 135 500 701 608 696 764 695 64 590 851 194 89 278 864 314 529 165 448 414 471...
result:
ok correct
Test #13:
score: 0
Accepted
time: 11ms
memory: 19816kb
input:
2 10 10000000 999 198 236 761 86 644 189 7 741 274 656 547 36 825 827 740 333 896 832 575 37 359 456 833 590 427 837 100 60 424 237 208 742 266 543 941 906 422 423 953 787 397 337 215 469 979 51 404 546 603 168 849 472 737 135 500 701 608 696 764 695 64 590 851 194 89 278 864 314 529 165 448 414 471...
result:
ok correct
Test #14:
score: 0
Accepted
time: 27ms
memory: 21696kb
input:
2 10 10000000 999 60 112 98 509 586 175 588 875 861 516 920 370 781 249 999 649 292 308 934 949 437 92 506 752 547 866 869 510 984 228 338 612 202 630 360 809 56 107 566 448 940 726 146 299 941 50 319 794 670 603 365 492 728 872 829 942 451 632 373 106 909 25 306 995 735 99 568 673 75 573 383 407 56...
result:
ok correct
Test #15:
score: 0
Accepted
time: 29ms
memory: 22208kb
input:
2 10 10000000 999 60 112 98 509 586 175 588 875 861 516 920 370 781 249 999 649 292 308 934 949 437 92 506 752 547 866 869 510 984 228 991 612 202 630 360 809 56 107 566 448 940 726 146 299 941 50 319 794 670 603 365 492 728 872 829 942 451 632 373 106 909 25 306 995 735 99 568 673 75 573 383 407 56...
result:
ok correct
Test #16:
score: 0
Accepted
time: 14ms
memory: 21176kb
input:
2 10 10000000 999 60 112 125 509 291 175 588 875 861 516 920 370 781 618 999 649 292 45 934 949 437 92 506 752 547 866 869 510 208 991 338 612 208 630 360 809 56 107 737 448 940 726 208 291 941 50 319 794 670 603 365 618 291 159 829 942 451 632 373 106 847 25 306 125 735 99 568 673 642 573 383 338 5...
result:
ok correct
Test #17:
score: 0
Accepted
time: 19ms
memory: 21152kb
input:
2 10 10000000 999 60 112 338 509 847 175 588 875 861 516 920 370 781 249 999 649 292 618 934 949 437 92 506 752 547 866 869 510 125 291 515 612 737 630 360 809 56 107 208 448 940 726 515 338 941 50 319 794 670 603 365 125 125 515 829 942 451 632 373 106 902 25 306 515 735 99 568 673 907 573 383 291 ...
result:
ok correct
Test #18:
score: 0
Accepted
time: 12ms
memory: 18384kb
input:
2 10 10000000 999 60 736 736 736 736 175 736 875 861 736 736 370 736 736 736 736 292 736 736 949 736 736 736 752 547 736 869 510 736 736 736 612 736 736 360 809 736 107 736 448 736 736 736 736 941 736 319 794 736 603 736 736 736 736 736 736 451 736 373 106 736 25 306 736 735 99 736 673 736 573 383 7...
result:
ok correct
Test #19:
score: 0
Accepted
time: 10ms
memory: 17444kb
input:
2 10 10000000 999 60 736 736 736 736 175 736 875 861 736 736 370 736 736 736 736 292 736 736 949 736 736 736 752 547 736 869 510 736 736 736 612 736 736 360 809 736 107 736 448 736 736 736 736 941 736 319 794 736 603 736 736 736 736 736 736 451 736 373 106 736 25 306 736 735 99 736 673 736 573 383 7...
result:
ok correct
Test #20:
score: 0
Accepted
time: 19ms
memory: 21312kb
input:
2 10 10000000 999 60 825 542 207 182 175 71 875 861 275 642 370 725 600 184 242 292 978 56 949 189 839 896 752 547 479 869 510 328 592 288 612 373 975 360 809 317 107 642 448 822 742 200 947 941 614 319 794 580 603 473 760 89 872 342 160 451 326 373 106 488 25 306 39 735 99 533 673 94 573 383 473 56...
result:
ok correct
Test #21:
score: 0
Accepted
time: 26ms
memory: 20220kb
input:
2 10 10000000 999 60 702 344 961 410 175 657 875 861 502 500 370 194 97 850 849 292 681 289 949 574 375 233 752 547 708 869 510 457 80 683 612 752 653 360 809 64 107 127 448 941 704 685 448 941 535 319 794 945 603 901 318 460 388 672 460 451 946 373 106 10 25 306 318 735 99 502 673 304 573 383 227 5...
result:
ok correct
Subtask #3:
score: 12
Accepted
Test #22:
score: 12
Accepted
time: 254ms
memory: 30332kb
input:
3 100 10000000 999 328 852 537 953 554 506 483 192 443 912 989 346 935 232 652 528 261 899 131 531 81 686 815 543 991 810 576 639 670 572 604 842 546 322 916 97 510 160 238 696 882 214 212 194 102 964 719 255 416 260 687 148 225 664 105 100 913 600 921 203 571 406 752 189 929 716 523 809 666 589 235...
result:
ok correct
Test #23:
score: 0
Accepted
time: 260ms
memory: 26844kb
input:
3 100 10000000 999 603 168 694 35 890 839 431 506 172 225 322 14 231 221 387 802 768 786 858 954 214 929 553 795 917 554 453 983 112 196 5 428 421 149 960 294 875 380 900 914 135 141 398 480 716 377 693 832 582 629 59 975 998 513 351 193 293 328 677 96 338 39 569 236 243 849 254 418 877 413 7 675 69...
result:
ok correct
Test #24:
score: 0
Accepted
time: 278ms
memory: 27012kb
input:
3 100 10000000 999 232 191 603 626 730 411 104 65 39 494 691 185 208 192 567 818 210 162 385 511 733 860 72 765 262 635 485 516 768 426 641 477 334 92 555 520 173 296 621 80 312 695 168 760 182 556 716 457 123 718 147 474 246 9 221 369 266 912 365 247 575 86 120 584 755 525 527 276 623 323 572 550 1...
result:
ok correct
Test #25:
score: 0
Accepted
time: 267ms
memory: 27976kb
input:
3 100 10000000 999 37 333 429 430 950 395 199 67 394 239 625 725 586 176 839 401 226 14 898 931 541 738 560 638 302 457 846 468 193 423 215 692 746 262 722 43 869 984 510 181 977 809 805 327 22 444 208 768 47 372 946 20 958 863 147 409 224 95 466 694 837 167 195 949 778 24 126 953 852 480 730 365 13...
result:
ok correct
Test #26:
score: 0
Accepted
time: 257ms
memory: 28564kb
input:
3 100 10000000 999 289 402 626 749 480 763 773 565 829 569 200 303 980 734 514 539 440 769 674 130 102 117 798 994 919 493 149 456 109 121 587 835 386 851 657 268 67 382 612 792 541 883 742 436 403 968 872 60 983 260 76 550 571 158 635 428 877 807 681 604 513 598 459 218 173 599 683 308 727 221 733 ...
result:
ok correct
Subtask #4:
score: 0
Wrong Answer
Test #27:
score: 17
Accepted
time: 261ms
memory: 27768kb
input:
4 100 10000000 999 710 227 715 954 623 585 538 236 363 913 540 3 897 998 726 919 976 843 796 69 415 705 647 707 201 696 993 545 325 375 47 260 490 385 828 162 29 278 867 593 395 219 178 518 999 685 307 772 224 187 557 89 575 524 1 157 230 341 708 978 473 995 15 179 743 416 263 640 4 851 520 719 679 ...
result:
ok correct
Test #28:
score: 0
Accepted
time: 279ms
memory: 25236kb
input:
4 100 10000000 999 714 793 831 566 274 202 861 272 583 533 805 725 138 636 832 242 737 219 191 168 939 364 439 770 290 84 581 419 991 431 892 387 487 753 368 627 900 476 934 316 854 802 898 48 741 182 950 684 121 881 996 120 917 311 386 63 377 300 734 333 789 257 797 134 668 490 649 843 795 198 462 ...
result:
ok correct
Test #29:
score: 0
Accepted
time: 236ms
memory: 26644kb
input:
4 100 10000000 999 118 434 443 62 975 789 284 936 885 652 937 50 912 733 854 532 772 709 407 312 535 589 419 247 190 474 469 905 165 889 13 159 189 746 837 603 181 335 880 513 496 897 887 442 498 656 838 342 522 93 771 816 178 541 788 215 586 794 267 297 938 853 244 255 640 654 101 470 621 232 162 8...
result:
ok correct
Test #30:
score: 0
Accepted
time: 241ms
memory: 25512kb
input:
4 100 10000000 999 418 71 357 515 696 936 943 436 645 53 344 262 706 201 896 877 732 738 433 684 891 641 264 615 32 659 990 529 219 165 81 420 22 61 35 704 233 339 201 42 816 126 522 561 960 673 452 720 99 328 222 423 804 226 266 652 291 939 981 503 209 275 653 525 812 886 693 343 881 353 218 227 28...
result:
ok correct
Test #31:
score: 0
Accepted
time: 74ms
memory: 22304kb
input:
4 100 10000000 999 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 388 3...
result:
ok correct
Test #32:
score: 0
Accepted
time: 75ms
memory: 22708kb
input:
4 100 10000000 999 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 195 1...
result:
ok correct
Test #33:
score: 0
Accepted
time: 245ms
memory: 27740kb
input:
4 100 10000000 999 962 472 490 254 571 779 648 83 213 290 889 914 69 311 578 495 455 361 519 832 796 230 588 172 320 357 123 142 703 590 9 669 728 63 829 749 585 11 131 478 744 657 605 614 942 267 108 587 852 148 491 757 256 450 739 16 174 556 94 810 582 426 562 482 629 699 529 152 278 176 696 443 1...
result:
ok correct
Test #34:
score: 0
Accepted
time: 252ms
memory: 28560kb
input:
4 100 10000000 999 331 37 14 256 432 435 352 197 67 971 655 165 874 457 295 488 626 393 163 563 4 429 747 656 765 513 516 290 380 444 519 302 829 781 74 981 557 880 828 200 135 213 928 711 574 487 575 477 134 239 17 349 269 751 552 853 668 558 625 789 921 553 114 677 187 775 333 379 670 314 88 472 7...
result:
ok correct
Test #35:
score: 0
Accepted
time: 130ms
memory: 25608kb
input:
4 100 10000000 999 934 685 993 853 853 853 219 485 853 283 784 756 242 853 853 163 759 277 278 853 438 853 657 412 853 853 707 13 853 853 853 853 166 715 853 853 853 853 853 724 853 392 853 858 121 853 630 853 760 974 428 853 853 853 429 853 565 226 853 853 853 179 853 853 796 308 853 853 717 466 81...
result:
ok correct
Test #36:
score: 0
Accepted
time: 136ms
memory: 25976kb
input:
4 100 10000000 999 477 839 786 681 539 786 786 786 786 786 786 786 590 321 786 786 872 161 332 786 786 786 786 822 786 786 786 786 786 170 940 134 240 786 835 786 874 18 786 786 786 786 786 957 396 327 786 786 786 414 786 581 310 772 494 786 53 786 158 786 786 786 786 107 786 780 786 602 786 786 786...
result:
ok correct
Test #37:
score: -17
Wrong Answer
time: 127ms
memory: 24292kb
input:
4 100 10000000 999 341 29 528 986 538 636 447 736 829 779 895 91 65 935 906 951 792 365 63 225 865 698 965 968 147 943 508 920 264 573 774 461 452 746 676 131 386 288 830 350 14 34 109 15 902 634 617 203 514 929 61 904 91 612 395 341 533 451 528 343 588 561 944 885 536 693 518 374 557 909 821 692 55...
result:
wrong answer
Subtask #5:
score: 0
Wrong Answer
Test #47:
score: 0
Wrong Answer
time: 1768ms
memory: 438440kb
input:
5 100 25000000 49999 3753 28650 36024 8322 47241 9061 43764 6338 45160 16765 40294 43358 37214 37535 38561 1997 7478 9543 11661 1953 7391 41171 43559 9981 24218 13155 22152 45216 30123 1843 20703 23601 42707 6449 40356 3761 32284 34584 32674 44391 41031 324 14845 6935 37071 38330 48041 1824 41182 46...
result:
wrong answer too many queries
Subtask #6:
score: 0
Wrong Answer
Test #52:
score: 0
Wrong Answer
time: 2978ms
memory: 288944kb
input:
6 100 40000000 9999 3929 7460 4617 7377 498 7572 4628 3661 2404 9179 755 4076 8531 6581 1929 9419 1498 4402 6412 712 4918 2628 798 6283 9427 9775 1472 5554 2146 9972 5228 5459 8417 6778 3121 7649 1031 7691 6270 2238 4885 6121 2099 3435 4615 9962 6384 8809 9169 4553 66 1939 8589 2029 4897 7334 2867 8...
result:
wrong answer too many queries
Subtask #7:
score: 0
Wrong Answer
Test #72:
score: 0
Wrong Answer
time: 2774ms
memory: 475200kb
input:
7 50 40000000 29999 12447 18709 13054 17585 8337 14953 7985 1930 24383 1787 2543 26860 12198 2842 14256 8665 17034 6429 14773 8646 27093 6362 29357 18001 10667 8445 6671 21435 27163 14604 19875 745 20772 6696 16391 15560 16789 10983 6199 23133 13 13688 14547 8390 4398 21653 14460 690 24385 5358 2213...
result:
wrong answer too many queries
Subtask #8:
score: 0
Memory Limit Exceeded
Test #92:
score: 0
Memory Limit Exceeded
input:
8 100 50000000 29999 8375 16777 16700 20953 11899 14682 20874 25860 28858 23241 5089 8044 25448 17746 5605 3087 9145 20179 1080 22944 27383 8384 19943 15371 27572 7882 23028 10474 18744 20202 15687 17001 7543 18709 23165 15713 17032 29011 22353 17455 26045 3484 20330 15159 21274 382 23927 20114 6303...