Submission details
Task:Tourist's Journey
Sender:Sebastian
Submission time:2026-04-16 10:36:02 +0300
Language:C++ (C++20)
Status:READY
Result:47
Feedback
subtaskverdictscore
#1ACCEPTED7
#20
#3ACCEPTED11
#4ACCEPTED29
#50
#60
Test results
testverdicttimesubtask
#1ACCEPTED0.00 s1, 2, 5, 6details
#2ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#3ACCEPTED0.01 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
#7ACCEPTED0.00 s1, 2, 5, 6details
#8ACCEPTED0.00 s1, 2, 5, 6details
#9ACCEPTED0.00 s1, 2, 5, 6details
#10ACCEPTED0.00 s2, 3, 4, 5, 6details
#110.00 s2, 5, 6details
#120.00 s2, 5, 6details
#130.00 s2, 5, 6details
#14ACCEPTED0.22 s3, 4, 6details
#15ACCEPTED0.22 s3, 4, 6details
#16ACCEPTED0.22 s3, 4, 6details
#17ACCEPTED0.22 s3, 4, 6details
#18ACCEPTED0.22 s3, 4, 6details
#19ACCEPTED0.22 s3, 4, 6details
#20ACCEPTED0.23 s3, 4, 6details
#21ACCEPTED0.22 s3, 4, 6details
#22ACCEPTED0.23 s3, 4, 6details
#23ACCEPTED0.22 s3, 4, 6details
#24ACCEPTED0.22 s3, 4, 6details
#25ACCEPTED0.22 s3, 4, 6details
#26ACCEPTED0.22 s3, 4, 6details
#27ACCEPTED0.24 s3, 4, 6details
#28ACCEPTED0.25 s4, 6details
#29ACCEPTED0.25 s4, 6details
#30ACCEPTED0.28 s4, 6details
#31ACCEPTED0.25 s4, 6details
#32ACCEPTED0.25 s4, 6details
#33ACCEPTED0.25 s4, 6details
#34ACCEPTED0.25 s4, 6details
#35ACCEPTED0.28 s4, 6details
#36ACCEPTED0.25 s4, 6details
#37ACCEPTED0.25 s4, 6details
#38ACCEPTED0.25 s4, 6details
#39ACCEPTED0.25 s4, 6details
#40ACCEPTED0.25 s4, 6details
#41ACCEPTED0.26 s4, 6details
#42ACCEPTED0.25 s4, 6details
#43ACCEPTED0.26 s4, 6details
#44ACCEPTED0.26 s4, 6details
#45ACCEPTED0.26 s4, 6details
#46ACCEPTED0.25 s4, 6details
#47ACCEPTED0.25 s4, 6details
#48ACCEPTED0.16 s4, 6details
#49ACCEPTED0.15 s4, 6details
#50ACCEPTED0.15 s4, 6details
#510.01 s5, 6details
#520.01 s5, 6details
#530.03 s5, 6details
#540.03 s5, 6details
#550.03 s5, 6details
#560.03 s5, 6details
#570.28 s6details
#580.37 s6details
#590.47 s6details
#600.30 s6details
#610.25 s6details
#620.24 s6details

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef __int128_t i128;
#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
const ll inf = 4e18;

vector<ll> bfs(vector<vector<ll>> &adj, ll s) {
    ll n = sz(adj);
    vector<ll> dist(n, inf);
    queue<ll> qu;
    dist[s] = 0;
    qu.push(s);
    while (sz(qu)) {
        ll i = qu.front(); qu.pop();
        for (auto &e : adj[i]) {
            if (dist[e] < inf) continue;
            dist[e] = dist[i] + 1;
            qu.push(e);
        }
    }
    return dist;
}

void solve() {
    ll n, m, k; cin >> n >> m >> k;
    vector<vector<ll>> adj(n);
    for (ll i = 0; i < m; i++) {
        ll u, v; cin >> u >> v; u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<bool> vis(n);
    vector<vector<ll>> tadj(n);
    vector<pll> bs;
    bs.emplace_back(0, 0);
    bs.emplace_back(n-1, n-1);
    auto dfs = [&](auto &oink, ll i, ll p) -> bool {
        if (vis[i]) return false;
        vis[i] = true;
        for (auto &e : adj[i]) {
            if (e == p) continue;
            if (oink(oink, e, i)) {
                tadj[i].push_back(e);
                tadj[e].push_back(i);
            }
            else {
                bs.emplace_back(i, e);
            }
        }
        return true;
    };
    dfs(dfs, 0, 0);

    vector<ll> xs;
    for (auto &[u, v] : bs) {
        xs.push_back(u);
        xs.push_back(v);
    }
    sort(all(xs));
    xs.erase(unique(all(xs)), xs.end());
    for (auto &[u, v] : bs) {
        u = lower_bound(all(xs), u) - xs.begin();
        v = lower_bound(all(xs), v) - xs.begin();
    }
    vector<vector<ll>> dist;
    for (auto &x : xs) {
        dist.push_back(bfs(tadj, x));
    }

    vector<ll> rev(sz(bs));
    for (ll i = 0; i < sz(bs); i++) {
        for (ll j = i+1; j < sz(bs); j++) {
            if (bs[i].first == bs[j].second && bs[i].second == bs[j].first) {
                rev[i] = j;
                rev[j] = i;
            }
        }
    }
    rev[0] = 0;
    rev[1] = 1;

    vector<vector<ll>> comb(sz(bs), vector<ll>(k+2));
    //vector<vector<ll>> cc(sz(bs), vector<ll>(k+1));
    ll K = k;
    comb[0][0] = 1;
    for (ll i = 0; i <= k; i++) {
        for (ll j = 0; j < sz(bs); j++) {
            for (ll k = 0; k < sz(bs); k++) {
                if (j == 1) continue;
                if (k == 0) continue;
                if (rev[j] == k) continue;
                ll t = i + dist[bs[j].second][xs[bs[k].first]] + 1;
                if (t > K+1) continue;
                comb[k][t] += comb[j][i];
            }
        }
    }

    cout << comb[1][k+1] << '\n';
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    solve();
}

Test details

Test 1

Subtask: 1, 2, 5, 6

Verdict: ACCEPTED

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

correct output
4

user output
4

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: ACCEPTED

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

correct output
414

user output
414

Test 8

Subtask: 1, 2, 5, 6

Verdict: ACCEPTED

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

correct output
15355

user output
15355

Test 9

Subtask: 1, 2, 5, 6

Verdict: ACCEPTED

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

correct output
8

user output
8

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
2238072730545106

Feedback: Incorrect character on line 1 col 1: expected "714878602", got "223807273054..."

Test 12

Subtask: 2, 5, 6

Verdict:

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

correct output
145213422

user output
6000723703133532065

Feedback: Incorrect character on line 1 col 1: expected "145213422", got "600072370313..."

Test 13

Subtask: 2, 5, 6

Verdict:

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

correct output
524970892

user output
259429746324181520

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

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
919857725643565378

Feedback: Incorrect character on line 1 col 2: expected "97138096", got "919857725643..."

Test 52

Subtask: 5, 6

Verdict:

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

correct output
841074570

user output
-542727573193665779

Feedback: Incorrect character on line 1 col 1: expected "841074570", got "-54272757319..."

Test 53

Subtask: 5, 6

Verdict:

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

correct output
724704425

user output
-5543561686995180615

Feedback: Incorrect character on line 1 col 1: expected "724704425", got "-55435616869..."

Test 54

Subtask: 5, 6

Verdict:

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

correct output
864991067

user output
-4662214191669571328

Feedback: Incorrect character on line 1 col 1: expected "864991067", got "-46622141916..."

Test 55

Subtask: 5, 6

Verdict:

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

correct output
970435703

user output
-6083189547490346009

Feedback: Incorrect character on line 1 col 1: expected "970435703", got "-60831895474..."

Test 56

Subtask: 5, 6

Verdict:

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

correct output
27240937

user output
7186706478541989356

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

Test 57

Subtask: 6

Verdict:

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

correct output
980044634

user output
1368098844438121440

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

Test 58

Subtask: 6

Verdict:

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

correct output
883528742

user output
-9101364786260262382

Feedback: Incorrect character on line 1 col 1: expected "883528742", got "-91013647862..."

Test 59

Subtask: 6

Verdict:

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

correct output
79062217

user output
-9171165336696674041

Feedback: Incorrect character on line 1 col 1: expected "79062217", got "-91711653366..."

Test 60

Subtask: 6

Verdict:

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

correct output
864991067

user output
-4662214191669571328

Feedback: Incorrect character on line 1 col 1: expected "864991067", got "-46622141916..."

Test 61

Subtask: 6

Verdict:

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

correct output
471882140

user output
3398392310260628142

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

Test 62

Subtask: 6

Verdict:

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

correct output
235428850

user output
-551496796025296780

Feedback: Incorrect character on line 1 col 1: expected "235428850", got "-55149679602..."