Submission details
Task:Tourist's Journey
Sender:RKondratavicius
Submission time:2026-04-16 14:36:29 +0300
Language:C++ (C++20)
Status:READY
Result:40
Feedback
subtaskverdictscore
#10
#20
#3ACCEPTED11
#4ACCEPTED29
#50
#60
Test results
testverdicttimesubtask
#10.00 s1, 2, 5, 6details
#2ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#3ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.00 s1, 2, 4, 5, 6details
#5ACCEPTED0.00 s1, 2, 4, 5, 6details
#6ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#70.00 s1, 2, 5, 6details
#80.00 s1, 2, 5, 6details
#90.00 s1, 2, 5, 6details
#10ACCEPTED0.00 s2, 3, 4, 5, 6details
#11--2, 5, 6details
#12--2, 5, 6details
#130.00 s2, 5, 6details
#14ACCEPTED0.25 s3, 4, 6details
#15ACCEPTED0.24 s3, 4, 6details
#16ACCEPTED0.23 s3, 4, 6details
#17ACCEPTED0.24 s3, 4, 6details
#18ACCEPTED0.24 s3, 4, 6details
#19ACCEPTED0.25 s3, 4, 6details
#20ACCEPTED0.23 s3, 4, 6details
#21ACCEPTED0.24 s3, 4, 6details
#22ACCEPTED0.24 s3, 4, 6details
#23ACCEPTED0.25 s3, 4, 6details
#24ACCEPTED0.24 s3, 4, 6details
#25ACCEPTED0.24 s3, 4, 6details
#26ACCEPTED0.24 s3, 4, 6details
#27ACCEPTED0.25 s3, 4, 6details
#28ACCEPTED0.24 s4, 6details
#29ACCEPTED0.25 s4, 6details
#30ACCEPTED0.26 s4, 6details
#31ACCEPTED0.25 s4, 6details
#32ACCEPTED0.25 s4, 6details
#33ACCEPTED0.22 s4, 6details
#34ACCEPTED0.24 s4, 6details
#35ACCEPTED0.22 s4, 6details
#36ACCEPTED0.26 s4, 6details
#37ACCEPTED0.27 s4, 6details
#38ACCEPTED0.26 s4, 6details
#39ACCEPTED0.28 s4, 6details
#40ACCEPTED0.26 s4, 6details
#41ACCEPTED0.26 s4, 6details
#42ACCEPTED0.27 s4, 6details
#43ACCEPTED0.28 s4, 6details
#44ACCEPTED0.25 s4, 6details
#45ACCEPTED0.30 s4, 6details
#46ACCEPTED0.28 s4, 6details
#47ACCEPTED0.31 s4, 6details
#48ACCEPTED0.17 s4, 6details
#49ACCEPTED0.21 s4, 6details
#50ACCEPTED0.20 s4, 6details
#510.01 s5, 6details
#520.01 s5, 6details
#53--5, 6details
#540.01 s5, 6details
#550.01 s5, 6details
#560.01 s5, 6details
#570.24 s6details
#580.24 s6details
#590.24 s6details
#600.21 s6details
#610.22 s6details
#620.17 s6details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:7:15: warning: unused variable 'mod' [-Wunused-variable]
    7 |     const int mod = 1e9+7;
      |               ^~~
input/code.cpp:122:20: warning: 'prrid' may be used uninitialized [-Wmaybe-uninitialized]
  122 |     k -= atst[prrid];
      |          ~~~~~~~~~~^
input/code.cpp:102:9: note: 'prrid' was declared here
  102 |     int prrid;
      |         ^~~~~
input/code.cpp:146:20: warning: 'pbrid' may be used uninitialized [-Wmaybe-uninitialized]
  146 |     k -= atst[pbrid];
      |          ~~~~~~~~~~^
input/code.cpp:126:9: note: 'pbrid' was declared here
  126 |     int pbrid;
      |         ^~~~~

Code

#include <bits/stdc++.h>

using namespace std;

int main()
{
    const int mod = 1e9+7;
    int n, m, k;
    cin >> n >> m >> k;
    int senask = k;
    int ats = 0;
    vector<int> kaimynai[n];
    for(int i=0; i<m; i++)
    {
        int x, y;
        cin >> x >> y;
        x--; y--;
        kaimynai[x].push_back(y);
        kaimynai[y].push_back(x);
    }
    if(m == n-1)
    {
        int atst[n];
        for(int i=0; i<n; i++) atst[i]=INT_MAX;
        atst[0]=0;
        queue<int> q;
        q.push(0);
        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            for(int i:kaimynai[x])
            {
                if(atst[i] == INT_MAX)
                {
                    atst[i] = atst[x]+1;
                    q.push(i);
                }
            }
        }
        if(atst[n-1] == k)
        {
            cout << 1;
        }
        else cout << 0;
        return 0;
    }

    int atst[n];
    int prev[n];
    bool ar_rate[n];
    for(int i=0; i<n; i++)
    {
        atst[i]=INT_MAX;
        prev[i] = -1;
        ar_rate[i]=0;
    }
    atst[0]=0;
    queue<pair<int, int>> Q;
    Q.push({0, -1});
    while(!Q.empty())
    {
        pair<int, int> t = Q.front();
        int x = t.first, pre = t.second;
        Q.pop();
        for(int i:kaimynai[x])
        {
            if(atst[i] == INT_MAX)
            {
                atst[i] = atst[x]+1;
                prev[i] = x;
                Q.push({i, x});
            }
            else if(i != pre)
            {
                ar_rate[i] = 1;
                ar_rate[x] = 1;
                if(atst[i] < atst[x])
                {
                    x = prev[x];
                }
                else if(atst[i] > atst[x])
                {
                    i = prev[i];
                }
                while(i!=x)
                {
                    ar_rate[i] = 1;
                    ar_rate[x] = 1;
                    i = prev[i];
                    x = prev[x];
                }
                ar_rate[x] = 1;
                break;
            }
        }
    }
    queue<int> q;
    for(int i=0; i<n; i++) atst[i]=INT_MAX;
    atst[0]=0;
    q.push(0);
    int prrid;
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        if(ar_rate[x])
        {
            prrid = x;
            break;
        }
        for(int i:kaimynai[x])
        {
            if(atst[i] == INT_MAX)
            {
                atst[i] = atst[x]+1;
                q.push(i);
            }
        }
    }
    while(!q.empty()) q.pop();
    k -= atst[prrid];
    for(int i=0; i<n; i++) atst[i]=INT_MAX;
    atst[n-1]=0;
    q.push(n-1);
    int pbrid;
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        if(ar_rate[x])
        {
            pbrid = x;
            break;
        }
        for(int i:kaimynai[x])
        {
            if(atst[i] == INT_MAX)
            {
                atst[i] = atst[x]+1;
                q.push(i);
            }
        }
    }
    while(!q.empty()) q.pop();
    k -= atst[pbrid];
    bool ar_taspats = 0;
    if(prrid == pbrid) ar_taspats = 1;

    if(ar_taspats)
    {
        fill(atst, atst+n, INT_MAX);
        atst[0]=0;
        q.push(0);
        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            if(x == n-1)
            {
                break;
            }
            for(int i:kaimynai[x])
            {
                if(atst[i] == INT_MAX && !ar_rate[i])
                {
                    atst[i] = atst[x]+1;
                    q.push(i);
                }
            }
        }
        if(atst[n-1] == senask) ats++;
    }

    int vienas=0, kitas=0;
    for(int i:kaimynai[prrid])
    {
        if(ar_taspats) break;
        if(ar_rate[i])
        {
            bool ar_buvo[n];
            fill(ar_buvo, ar_buvo+n, 0);
            fill(atst, atst+n, INT_MAX);
            q.push(i);
            atst[i]=1;
            ar_buvo[prrid] = 1;
            while(!q.empty())
            {
                int x = q.front();
                q.pop();
                ar_buvo[x] = 1;
                if(x == pbrid)
                {
                    if(vienas == 0)
                        vienas = atst[x];
                    else
                        kitas = atst[x];
                    break;
                }
                for(int j:kaimynai[x])
                {
                    if(!ar_buvo[j] && ar_rate[j])
                    {
                        atst[j] = atst[x]+1;
                        q.push(j);
                    }
                }
            }
            while(!q.empty()) q.pop();
        }
    }
    int rato_ilgis = 0;
    for(int i=0; i<n; i++)
    {
        if(ar_rate[i]) rato_ilgis++;
    }
    if((k-vienas)%rato_ilgis==0 && k >= vienas) ats++;
    if((k-kitas)%rato_ilgis==0 && k >= kitas) ats++;
    //cout << k << ' ' << vienas << ' ' << kitas << ' ' << rato_ilgis << endl;
    cout << ats;
    return 0;
}
/*
8 8 8
1 2
2 8
2 4
4 5
5 6
6 3
4 7
7 6
*/

Test details

Test 1

Subtask: 1, 2, 5, 6

Verdict:

input
4 5 5
1 2
1 3
2 3
2 4
...

correct output
4

user output
1

Feedback: Incorrect character on line 1 col 1: expected "4", got "1"

Test 2

Subtask: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
4 3 4
1 2
2 3
2 4

correct output
0

user output
0

Test 3

Subtask: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
2 1 1
1 2

correct output
1

user output
1

Test 4

Subtask: 1, 2, 4, 5, 6

Verdict: ACCEPTED

input
10 10 5
9 2
9 4
2 5
8 9
...

correct output
0

user output
0

Test 5

Subtask: 1, 2, 4, 5, 6

Verdict: ACCEPTED

input
10 10 9
8 1
8 7
6 9
3 8
...

correct output
1

user output
1

Test 6

Subtask: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10 9 10
1 10
1 7
3 10
9 5
...

correct output
0

user output
0

Test 7

Subtask: 1, 2, 5, 6

Verdict:

input
10 15 10
5 8
9 10
2 6
7 8
...

correct output
414

user output
0

Feedback: Incorrect character on line 1 col 1: expected "414", got "0"

Test 8

Subtask: 1, 2, 5, 6

Verdict:

input
10 20 10
7 5
7 8
1 7
10 7
...

correct output
15355

user output
0

Feedback: Incorrect character on line 1 col 1: expected "15355", got "0"

Test 9

Subtask: 1, 2, 5, 6

Verdict:

input
10 12 10
8 7
9 8
10 5
5 1
...

correct output
8

user output
0

Feedback: Incorrect character on line 1 col 1: expected "8", got "0"

Test 10

Subtask: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
100 99 100
52 8
18 61
38 94
46 100
...

correct output
0

user output
0

Test 11

Subtask: 2, 5, 6

Verdict:

input
100 105 100
63 66
58 60
82 95
10 66
...

correct output
714878602

user output
(empty)

Test 12

Subtask: 2, 5, 6

Verdict:

input
100 110 100
27 10
36 41
21 51
67 70
...

correct output
145213422

user output
(empty)

Test 13

Subtask: 2, 5, 6

Verdict:

input
100 110 100
96 51
4 38
71 100
19 93
...

correct output
524970892

user output
0

Feedback: Incorrect character on line 1 col 1: expected "524970892", got "0"

Test 14

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
200000 199999 1
134991 60803
22509 116499
162563 3398
95539 36685
...

correct output
1

user output
1

Test 15

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
200000 199999 1
179534 8479
157903 75758
191654 70014
74093 136641
...

correct output
0

user output
0

Test 16

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
200000 199999 2
73737 181461
152353 164598
39854 152630
113800 102119
...

correct output
0

user output
0

Test 17

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
200000 199999 5
1864 74634
151242 167689
134304 34907
31191 144500
...

correct output
1

user output
1

Test 18

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
200000 199999 9582
81551 192132
19534 104640
189666 4048
159986 163627
...

correct output
0

user output
0

Test 19

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
200000 199999 634
120113 131941
86436 121516
73453 144867
154099 187559
...

correct output
1

user output
1

Test 20

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
200000 199999 9999
156360 44775
133399 102816
97578 115279
85426 35248
...

correct output
0

user output
0

Test 21

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
200000 199999 10000
174018 18095
124289 134248
156163 61487
22692 183062
...

correct output
0

user output
0

Test 22

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
200000 199999 9997
42421 142257
68681 66852
23753 189835
15920 152107
...

correct output
1

user output
1

Test 23

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
200000 199999 9997
7257 67775
137368 35287
136873 55062
139502 13649
...

correct output
0

user output
0

Test 24

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
200000 199999 10000
138530 194578
170092 135913
197846 30945
175841 29908
...

correct output
0

user output
0

Test 25

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
200000 199999 10000
50586 65889
97656 199
82172 169565
135247 49398
...

correct output
1

user output
1

Test 26

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
200000 199999 10000
26219 140202
80751 156885
89074 31121
39686 45438
...

correct output
0

user output
0

Test 27

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
200000 199999 10000
73458 26638
24960 73149
98500 100006
135056 25566
...

correct output
0

user output
0

Test 28

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 4
71063 170999
112262 167446
132778 41726
14927 149461
...

correct output
2

user output
2

Test 29

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 9997
93623 73104
143620 21837
140012 178958
169412 155227
...

correct output
0

user output
0

Test 30

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 9998
108676 85251
120626 53865
22185 185980
120315 133527
...

correct output
1

user output
1

Test 31

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 9999
34043 45894
188478 191792
179114 18866
92725 139966
...

correct output
1

user output
1

Test 32

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 10000
9844 33090
72074 105502
69473 85213
51479 27126
...

correct output
0

user output
0

Test 33

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 8
198227 52374
153592 94277
62798 198081
9747 38403
...

correct output
2

user output
2

Test 34

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 9999
38948 87012
75557 104481
136914 651
63353 76448
...

correct output
0

user output
0

Test 35

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 10000
114749 43409
197006 178268
178476 26621
148333 1852
...

correct output
2

user output
2

Test 36

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 9849
128248 41928
102409 136212
21468 167482
162722 46907
...

correct output
1

user output
1

Test 37

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 9850
180582 124939
11693 87470
171894 114673
151571 38440
...

correct output
0

user output
0

Test 38

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 9850
184412 83268
128807 44170
26253 126339
120550 69131
...

correct output
2

user output
2

Test 39

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 10000
116047 12970
63831 182104
111914 38753
145557 89749
...

correct output
2

user output
2

Test 40

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 10000
161162 192005
173486 5799
121169 117517
131073 50233
...

correct output
1

user output
1

Test 41

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 9999
161162 192005
173486 5799
121169 117517
131073 50233
...

correct output
0

user output
0

Test 42

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 9999
121115 10494
196280 116808
144717 31998
130883 84826
...

correct output
1

user output
1

Test 43

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 9998
121115 10494
196280 116808
144717 31998
130883 84826
...

correct output
0

user output
0

Test 44

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 10000
157121 120558
112994 175263
171516 106269
163986 185595
...

correct output
2

user output
2

Test 45

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 9999
15645 65909
109001 114704
48122 116792
138487 55081
...

correct output
0

user output
0

Test 46

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 10000
78578 123492
77698 40519
84219 64149
93230 51551
...

correct output
2

user output
2

Test 47

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 10000
125797 61162
25525 189681
178938 104343
127938 99958
...

correct output
0

user output
0

Test 48

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 10000
1 63340
1 117445
113745 1
194456 1
...

correct output
2

user output
2

Test 49

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 10000
146958 200000
200000 54040
68156 200000
200000 55718
...

correct output
2

user output
2

Test 50

Subtask: 4, 6

Verdict: ACCEPTED

input
200000 200000 10000
75759 1
1 122977
1 108735
1 44452
...

correct output
0

user output
0

Test 51

Subtask: 5, 6

Verdict:

input
1000 1001 10000
270 328
167 836
209 262
544 73
...

correct output
97138096

user output
0

Feedback: Incorrect character on line 1 col 1: expected "97138096", got "0"

Test 52

Subtask: 5, 6

Verdict:

input
1000 1005 10000
136 141
633 688
219 129
341 622
...

correct output
841074570

user output
0

Feedback: Incorrect character on line 1 col 1: expected "841074570", got "0"

Test 53

Subtask: 5, 6

Verdict:

input
1000 1010 10000
173 575
691 507
521 654
269 631
...

correct output
724704425

user output
(empty)

Test 54

Subtask: 5, 6

Verdict:

input
1000 1010 10000
904 1000
236 1000
1000 316
1000 948
...

correct output
864991067

user output
0

Feedback: Incorrect character on line 1 col 1: expected "864991067", got "0"

Test 55

Subtask: 5, 6

Verdict:

input
1000 1010 10000
431 889
501 636
7 582
462 868
...

correct output
970435703

user output
0

Feedback: Incorrect character on line 1 col 1: expected "970435703", got "0"

Test 56

Subtask: 5, 6

Verdict:

input
1000 1010 10000
246 207
963 273
738 223
695 924
...

correct output
27240937

user output
0

Feedback: Incorrect character on line 1 col 1: expected "27240937", got "0"

Test 57

Subtask: 6

Verdict:

input
200000 200001 10000
73346 12940
91788 126866
191845 196823
1771 45039
...

correct output
980044634

user output
0

Feedback: Incorrect character on line 1 col 1: expected "980044634", got "0"

Test 58

Subtask: 6

Verdict:

input
200000 200005 10000
97853 177374
174818 82833
175749 181739
160817 150566
...

correct output
883528742

user output
0

Feedback: Incorrect character on line 1 col 1: expected "883528742", got "0"

Test 59

Subtask: 6

Verdict:

input
200000 200010 10000
8593 121197
90934 103451
173940 157010
55274 145619
...

correct output
79062217

user output
0

Feedback: Incorrect character on line 1 col 1: expected "79062217", got "0"

Test 60

Subtask: 6

Verdict:

input
200000 200010 10000
138445 200000
41553 200000
141229 200000
53521 200000
...

correct output
864991067

user output
2

Feedback: Incorrect character on line 1 col 1: expected "864991067", got "2"

Test 61

Subtask: 6

Verdict:

input
200000 200010 10000
9917 200000
24783 200000
200000 39037
14350 37168
...

correct output
471882140

user output
0

Feedback: Incorrect character on line 1 col 1: expected "471882140", got "0"

Test 62

Subtask: 6

Verdict:

input
200000 200010 10000
80269 156844
9747 1
104448 1
1 134193
...

correct output
235428850

user output
0

Feedback: Incorrect character on line 1 col 1: expected "235428850", got "0"