QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#952998#10253. Anime Shopsjiangly (Lingyu Jiang)100 ✓178ms18600kbC++231.5kb2025-03-27 14:44:012025-03-27 14:44:02

Judging History

This is the latest submission verdict.

  • [2025-03-27 14:44:02]
  • Judged
  • Verdict: 100
  • Time: 178ms
  • Memory: 18600kb
  • [2025-03-27 14:44:01]
  • Submitted

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