QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#952998 | #10253. Anime Shops | jiangly (Lingyu Jiang) | 100 ✓ | 178ms | 18600kb | C++23 | 1.5kb | 2025-03-27 14:44:01 | 2025-03-27 14:44:02 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using i128 = __int128;
using u128 = unsigned __int128;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, k;
std::cin >> n >> m >> k;
std::vector<bool> f(n);
for (int i = 0; i < k; i++) {
int x;
std::cin >> x;
x--;
f[x] = true;
}
std::vector<std::vector<int>> adj(n);
for (int i = 0; i < m; i++) {
int a, b;
std::cin >> a >> b;
a--;
b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
std::vector dis(n, std::array<std::array<int, 2>, 2> {-1, -1, -1, -1});
std::priority_queue<std::array<int, 3>, std::vector<std::array<int, 3>>, std::greater<>> pq;
for (int i = 0; i < n; i++) {
if (f[i]) {
pq.push({0, i, i});
}
}
while (!pq.empty()) {
auto [d, x, s] = pq.top();
pq.pop();
if (dis[x][1][0] != -1) {
continue;
}
if (s == dis[x][0][1]) {
continue;
}
if (dis[x][0][0] == -1) {
dis[x][0] = {d, s};
} else {
dis[x][1] = {d, s};
}
for (auto y : adj[x]) {
pq.push({d + 1, y, s});
}
}
for (int i = 0; i < n; i++) {
std::cout << dis[i][f[i]][0] << " \n"[i == n - 1];
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 23
Accepted
Test #1:
score: 23
Accepted
time: 0ms
memory: 3712kb
input:
1000 2000 1 736 1 868 976 995 377 536 973 976 605 668 829 865 575 753 628 758 286 786 587 876 750 769 858 864 755 949 698 970 864 865 323 502 671 825 451 649 382 531 411 425 402 720 318 407 622 835 430 526 973 985 678 899 199 419 427 433 344 489 797 804 880 993 903 979 663 838 270 283 253 477 855 93...
output:
4 5 5 5 5 3 -1 5 4 4 4 6 5 3 6 5 6 -1 2 4 -1 5 5 -1 -1 5 6 5 5 5 4 6 4 -1 5 -1 5 4 -1 4 -1 5 -1 4 5 5 -1 5 -1 6 6 6 5 6 6 5 3 5 5 3 4 -1 6 6 5 8 4 5 5 6 5 5 5 5 5 5 4 7 5 6 5 5 -1 4 3 6 -1 6 5 5 6 -1 -1 7 5 6 -1 -1 -1 5 -1 4 5 6 4 4 5 5 5 4 4 5 -1 5 4 -1 9 6 4 5 5 5 4 5 5 3 3 -1 5 7 4 4 5 6 4 6 -1 5...
result:
ok 1000 numbers
Test #2:
score: 23
Accepted
time: 2ms
memory: 3840kb
input:
1000 2000 20 507 955 340 813 418 505 753 914 430 603 599 631 951 882 539 365 205 346 605 757 120 275 839 881 462 853 126 468 536 716 297 814 176 979 80 303 199 365 430 672 642 900 88 865 716 816 102 429 176 454 713 830 885 892 983 986 653 833 478 940 88 237 559 881 181 360 514 920 609 649 833 895 32...
output:
5 7 4 1 4 3 -1 3 3 3 4 3 1 3 -1 4 4 3 4 2 -1 4 3 4 4 4 -1 2 3 2 3 4 2 -1 3 -1 -1 3 4 3 5 3 5 2 3 4 5 4 4 5 4 3 2 4 2 4 3 2 2 3 2 2 3 5 3 3 3 2 3 5 4 3 3 3 2 1 2 -1 3 3 3 -1 2 2 3 3 3 3 4 5 3 1 3 4 2 4 4 2 3 -1 4 3 3 5 3 1 3 3 3 3 2 3 2 4 5 3 3 4 3 4 4 2 4 1 2 4 2 5 3 3 4 3 4 4 3 2 3 3 4 2 2 3 1 4 4 ...
result:
ok 1000 numbers
Test #3:
score: 23
Accepted
time: 1ms
memory: 3968kb
input:
1000 2000 100 974 230 440 752 977 500 126 356 402 244 51 871 828 207 199 672 747 667 728 55 301 110 618 477 963 91 877 107 572 517 75 317 584 745 770 513 838 263 425 89 969 749 909 860 662 169 654 354 21 789 528 676 158 193 801 463 591 781 206 294 989 813 298 967 134 269 701 887 890 991 35 404 362 4...
output:
3 4 4 3 3 3 2 3 2 2 -1 -1 2 3 2 2 3 1 2 -1 3 1 3 4 1 3 -1 -1 3 -1 3 4 2 1 2 3 2 -1 3 1 2 2 2 3 2 3 2 2 2 3 1 1 1 -1 2 3 2 -1 4 3 2 2 -1 -1 2 2 2 2 1 -1 1 2 2 1 3 1 2 1 2 1 -1 3 2 2 2 2 2 -1 -1 3 2 2 3 2 4 -1 2 3 2 2 1 -1 2 2 2 3 2 3 1 2 3 2 -1 4 2 1 2 1 2 3 3 2 3 2 1 2 3 -1 3 1 2 -1 3 3 -1 2 2 2 2 1...
result:
ok 1000 numbers
Test #4:
score: 23
Accepted
time: 2ms
memory: 3968kb
input:
1000 2000 1000 944 778 68 545 548 487 319 382 708 199 26 699 275 12 724 924 950 513 495 297 501 843 352 758 132 486 445 344 400 411 388 139 9 506 131 803 61 488 130 305 953 354 805 339 601 407 24 536 458 861 17 78 650 500 617 738 453 379 673 962 6 677 196 490 771 743 780 277 723 504 51 888 714 719 2...
output:
1 -1 1 1 -1 1 1 1 -1 1 1 1 -1 1 1 -1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
result:
ok 1000 numbers
Subtask #2:
score: 16
Accepted
Test #5:
score: 16
Accepted
time: 35ms
memory: 10480kb
input:
100000 99999 20 31889 17185 28446 14857 59379 73567 22978 42119 48355 81893 31624 9697 21434 50596 22495 55952 80188 37609 60038 45586 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31...
output:
9696 9695 9694 9693 9692 9691 9690 9689 9688 9687 9686 9685 9684 9683 9682 9681 9680 9679 9678 9677 9676 9675 9674 9673 9672 9671 9670 9669 9668 9667 9666 9665 9664 9663 9662 9661 9660 9659 9658 9657 9656 9655 9654 9653 9652 9651 9650 9649 9648 9647 9646 9645 9644 9643 9642 9641 9640 9639 9638 9637 ...
result:
ok 100000 numbers
Test #6:
score: 16
Accepted
time: 57ms
memory: 14056kb
input:
100000 99999 100000 31889 17185 28446 14857 59379 73567 22978 42119 48355 81893 31624 9697 21434 50596 22495 55952 80188 37609 60038 45586 76848 28409 82535 62021 47723 19754 55200 94167 50070 82750 37307 19965 56154 30835 54630 34521 11403 88139 60946 7397 60168 3950 36245 46725 61156 3635 50947 70...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 numbers
Test #7:
score: 16
Accepted
time: 16ms
memory: 10348kb
input:
100000 99999 1 31889 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...
output:
31888 31887 31886 31885 31884 31883 31882 31881 31880 31879 31878 31877 31876 31875 31874 31873 31872 31871 31870 31869 31868 31867 31866 31865 31864 31863 31862 31861 31860 31859 31858 31857 31856 31855 31854 31853 31852 31851 31850 31849 31848 31847 31846 31845 31844 31843 31842 31841 31840 31839 ...
result:
ok 100000 numbers
Subtask #3:
score: 61
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #8:
score: 61
Accepted
time: 21ms
memory: 10356kb
input:
100000 99999 3 99998 99999 100000 1 2 1 3 1 4 2 5 3 6 4 7 5 8 6 9 7 10 8 11 9 12 10 13 11 14 12 15 13 16 14 17 15 18 16 19 17 20 18 21 19 22 20 23 21 24 22 25 23 26 24 27 25 28 26 29 27 30 28 31 29 32 30 33 31 34 32 35 33 36 34 37 35 38 36 39 37 40 38 41 39 42 40 43 41 44 42 45 43 46 44 47 45 48 46 ...
output:
33333 33332 33332 33332 33331 33331 33331 33330 33330 33330 33329 33329 33329 33328 33328 33328 33327 33327 33327 33326 33326 33326 33325 33325 33325 33324 33324 33324 33323 33323 33323 33322 33322 33322 33321 33321 33321 33320 33320 33320 33319 33319 33319 33318 33318 33318 33317 33317 33317 33316 ...
result:
ok 100000 numbers
Test #9:
score: 61
Accepted
time: 40ms
memory: 10484kb
input:
100000 99999 300 99701 99702 99703 99704 99705 99706 99707 99708 99709 99710 99711 99712 99713 99714 99715 99716 99717 99718 99719 99720 99721 99722 99723 99724 99725 99726 99727 99728 99729 99730 99731 99732 99733 99734 99735 99736 99737 99738 99739 99740 99741 99742 99743 99744 99745 99746 99747 9...
output:
333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 ...
result:
ok 100000 numbers
Test #10:
score: 61
Accepted
time: 49ms
memory: 12132kb
input:
100000 99999 30000 70001 70002 70003 70004 70005 70006 70007 70008 70009 70010 70011 70012 70013 70014 70015 70016 70017 70018 70019 70020 70021 70022 70023 70024 70025 70026 70027 70028 70029 70030 70031 70032 70033 70034 70035 70036 70037 70038 70039 70040 70041 70042 70043 70044 70045 70046 70047...
output:
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
result:
ok 100000 numbers
Test #11:
score: 61
Accepted
time: 13ms
memory: 8888kb
input:
100000 0 100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 100000 numbers
Test #12:
score: 61
Accepted
time: 18ms
memory: 10436kb
input:
100000 100000 2 1 50001 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50...
output:
50000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...
result:
ok 100000 numbers
Test #13:
score: 61
Accepted
time: 90ms
memory: 15008kb
input:
100000 200000 1 77222 58980 76263 59470 61811 43092 48939 14395 19964 6599 18917 72493 86256 91857 94575 20555 90990 83004 91529 59073 90109 19603 27136 44917 82804 26302 28679 58578 67603 3869 83717 31991 47462 47556 96320 64773 67786 94498 97657 80660 90998 35384 79148 66586 85039 85605 91353 1533...
output:
7 9 8 8 9 9 9 8 -1 7 9 9 -1 9 7 7 7 10 10 8 -1 7 9 7 8 9 7 7 9 8 8 9 8 10 8 9 7 8 6 7 7 8 9 7 9 8 8 8 7 9 10 -1 9 8 8 9 8 7 8 7 8 8 -1 -1 10 9 9 8 10 7 8 -1 9 8 -1 8 7 8 9 -1 -1 8 8 9 7 10 -1 8 9 7 9 8 8 8 8 7 9 8 8 7 8 7 7 7 10 8 -1 8 9 9 8 -1 8 -1 -1 8 8 9 8 10 9 8 8 9 9 -1 8 7 -1 6 9 8 8 8 9 8 8 ...
result:
ok 100000 numbers
Test #14:
score: 61
Accepted
time: 164ms
memory: 18596kb
input:
100000 200000 20 70440 82302 64483 96767 51485 50097 4612 736 51342 24972 98584 69084 26305 41520 57831 4749 92888 9662 3292 12448 57489 61316 56965 88375 13718 18029 40943 71301 29857 55799 7226 50633 35952 77227 3425 61895 55345 96014 14993 61759 87332 98065 32104 98424 95344 98503 23282 70398 492...
output:
5 -1 7 -1 7 6 6 9 5 5 5 6 7 6 -1 7 5 -1 6 6 6 6 -1 4 6 6 7 6 6 5 -1 -1 -1 5 -1 5 6 5 5 6 -1 6 -1 5 8 8 8 7 7 5 6 4 7 8 5 6 6 6 6 7 6 6 6 7 6 5 -1 7 6 -1 5 7 7 7 7 7 -1 7 7 -1 6 5 -1 7 6 7 6 5 6 7 7 6 5 -1 5 6 -1 7 5 6 4 -1 5 -1 7 3 6 6 7 5 4 -1 6 -1 7 8 6 4 7 6 8 -1 6 4 -1 5 6 6 7 6 5 6 6 -1 5 7 5 6...
result:
ok 100000 numbers
Test #15:
score: 61
Accepted
time: 160ms
memory: 18600kb
input:
100000 200000 100 68738 37820 55519 77758 46482 88425 97912 55476 55207 32059 54145 49530 70919 47725 2212 44552 41417 41082 55379 54864 57467 30308 11765 22915 69152 25111 38968 98696 15910 88769 97877 48925 19948 30737 1399 69967 8251 92550 30545 31372 57947 70569 9851 73690 94619 68799 91067 7064...
output:
4 6 4 4 3 4 2 -1 6 6 4 5 4 5 5 5 6 4 2 6 4 5 4 5 5 4 6 4 6 5 -1 5 5 4 5 -1 5 4 -1 4 4 6 4 4 6 4 -1 6 5 5 4 -1 6 6 6 5 5 -1 4 -1 6 7 5 5 5 -1 6 6 5 6 4 5 6 6 7 4 -1 5 5 -1 -1 5 6 5 6 -1 5 6 4 4 6 4 5 5 5 6 5 3 5 5 7 5 6 5 -1 5 6 5 5 4 -1 5 6 6 5 5 3 -1 6 6 -1 7 5 6 4 -1 4 2 4 6 4 6 4 6 5 -1 -1 3 -1 5...
result:
ok 100000 numbers
Test #16:
score: 61
Accepted
time: 178ms
memory: 18588kb
input:
100000 200000 100000 47137 80136 73346 78144 9205 62735 86344 13199 80186 64994 68131 30929 68948 60314 18829 36275 73333 78367 65060 98790 56756 84155 35516 26090 12224 59296 62554 48634 60091 95216 86161 12524 99931 2369 91665 49795 38108 12619 27029 66122 81611 97253 86450 48561 85515 33799 53223...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 ...
result:
ok 100000 numbers