Submission details
Task:Tourist's Journey
Sender:Diego_09
Submission time:2026-04-16 14:14:54 +0300
Language:C++ (C++17)
Status:READY
Result:7
Feedback
subtaskverdictscore
#1ACCEPTED7
#20
#30
#40
#50
#60
Test results
testverdicttimesubtask
#1ACCEPTED0.02 s1, 2, 5, 6details
#2ACCEPTED0.02 s1, 2, 3, 4, 5, 6details
#3ACCEPTED0.02 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.02 s1, 2, 4, 5, 6details
#5ACCEPTED0.02 s1, 2, 4, 5, 6details
#6ACCEPTED0.02 s1, 2, 3, 4, 5, 6details
#7ACCEPTED0.02 s1, 2, 5, 6details
#8ACCEPTED0.02 s1, 2, 5, 6details
#9ACCEPTED0.02 s1, 2, 5, 6details
#10ACCEPTED0.02 s2, 3, 4, 5, 6details
#11ACCEPTED0.02 s2, 5, 6details
#120.02 s2, 5, 6details
#130.02 s2, 5, 6details
#140.11 s3, 4, 6details
#150.11 s3, 4, 6details
#160.12 s3, 4, 6details
#170.12 s3, 4, 6details
#180.11 s3, 4, 6details
#190.11 s3, 4, 6details
#200.12 s3, 4, 6details
#210.12 s3, 4, 6details
#220.11 s3, 4, 6details
#230.12 s3, 4, 6details
#240.11 s3, 4, 6details
#250.11 s3, 4, 6details
#260.11 s3, 4, 6details
#270.11 s3, 4, 6details
#280.11 s4, 6details
#290.11 s4, 6details
#300.12 s4, 6details
#310.11 s4, 6details
#320.11 s4, 6details
#330.11 s4, 6details
#340.12 s4, 6details
#350.11 s4, 6details
#360.11 s4, 6details
#370.11 s4, 6details
#380.12 s4, 6details
#390.12 s4, 6details
#400.11 s4, 6details
#410.11 s4, 6details
#420.12 s4, 6details
#430.11 s4, 6details
#440.11 s4, 6details
#450.12 s4, 6details
#460.11 s4, 6details
#470.12 s4, 6details
#480.09 s4, 6details
#490.09 s4, 6details
#500.08 s4, 6details
#510.02 s5, 6details
#520.02 s5, 6details
#530.02 s5, 6details
#540.02 s5, 6details
#550.02 s5, 6details
#560.02 s5, 6details
#570.11 s6details
#580.11 s6details
#590.11 s6details
#600.09 s6details
#610.09 s6details
#620.08 s6details

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#if defined(__has_include)&&__has_include("custom_h/debugging.h")
#define local_run 1
#include "custom_h\debugging.h"
#else 
#define local_run 0
#endif
// #pragma GCC target ("avx2");
// #pragma GCC optimize ("Ofast");
#define rall(v) v.rbegin(),v.rend()
#define all(v) v.begin(),v.end()
#define keyval find_by_order
#define valkey order_of_key
#define int long long
#define pb push_back
#define s second
#define f first

using namespace __gnu_pbds; 
using namespace std;
template<typename T>
using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename T>
using omset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
    
void set_io(string name=""){
    ios_base::sync_with_stdio(0);cin.tie(0);
    if(name.size() and !local_run){
        // freopen((name+".in").c_str(),"r",stdin);
        // freopen((name+".out").c_str(),"w",stdout);
    }
}

const int my[]={0,0,1,-1,1,1,-1,-1};
const int mx[]={1,-1,0,0,1,-1,-1,1};
const int md=1e9+7;
const int oo=1e18;

vector<int>graph[200001];
vector<vector<vector<int>>>dp(111,vector<vector<int>>(111,vector<int>(111,0)));;
int n,m,k;

int bfs(){
    priority_queue<pair<int,pair<int,int>>>q;
    q.push({0,{1,106}});
    dp[1][0][106]=1;
    int ans=0;

    while(!q.empty()){
        int d=-q.top().f;
        int x=q.top().s.f;
        int p=q.top().s.s;
        q.pop();

        // cerr<<"x:"<<x<<" d:"<<d<<" p:"<<p<<" s:"<<dp[x][d][p]<<"\n";

        if(d==k){
            if(x==n)ans+=dp[x][d][p];
            ans%=md;
            continue;
        }

        for(int i:graph[x]){
            if(i==p)continue;
            
            if(dp[i][d+1][x]==0)q.push({-(d+1),{i,x}});
            dp[i][d+1][x]+=dp[x][d][p];
        }
    }
    return ans;
}

void solve(){
    cin>>n>>m>>k;

    while(m--){
        int a,b;
        cin>>a>>b;
        graph[a].pb(b);
        graph[b].pb(a);
    }

    cout<<bfs();
    return;
}

int32_t main(){set_io("");
    int t=1;
    // cin>>t;
    while(t--){
        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: ACCEPTED

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

correct output
714878602

user output
714878602

Test 12

Subtask: 2, 5, 6

Verdict:

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

correct output
145213422

user output
128466438

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

Test 13

Subtask: 2, 5, 6

Verdict:

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

correct output
524970892

user output
-403546714

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

Test 14

Subtask: 3, 4, 6

Verdict:

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

correct output
1

user output
(empty)

Test 15

Subtask: 3, 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 16

Subtask: 3, 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 17

Subtask: 3, 4, 6

Verdict:

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

correct output
1

user output
(empty)

Test 18

Subtask: 3, 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 19

Subtask: 3, 4, 6

Verdict:

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

correct output
1

user output
(empty)

Test 20

Subtask: 3, 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 21

Subtask: 3, 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 22

Subtask: 3, 4, 6

Verdict:

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

correct output
1

user output
(empty)

Test 23

Subtask: 3, 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 24

Subtask: 3, 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 25

Subtask: 3, 4, 6

Verdict:

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

correct output
1

user output
(empty)

Test 26

Subtask: 3, 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 27

Subtask: 3, 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 28

Subtask: 4, 6

Verdict:

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

correct output
2

user output
(empty)

Test 29

Subtask: 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 30

Subtask: 4, 6

Verdict:

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

correct output
1

user output
(empty)

Test 31

Subtask: 4, 6

Verdict:

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

correct output
1

user output
(empty)

Test 32

Subtask: 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 33

Subtask: 4, 6

Verdict:

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

correct output
2

user output
(empty)

Test 34

Subtask: 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 35

Subtask: 4, 6

Verdict:

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

correct output
2

user output
(empty)

Test 36

Subtask: 4, 6

Verdict:

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

correct output
1

user output
(empty)

Test 37

Subtask: 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 38

Subtask: 4, 6

Verdict:

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

correct output
2

user output
(empty)

Test 39

Subtask: 4, 6

Verdict:

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

correct output
2

user output
(empty)

Test 40

Subtask: 4, 6

Verdict:

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

correct output
1

user output
(empty)

Test 41

Subtask: 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 42

Subtask: 4, 6

Verdict:

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

correct output
1

user output
(empty)

Test 43

Subtask: 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 44

Subtask: 4, 6

Verdict:

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

correct output
2

user output
(empty)

Test 45

Subtask: 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 46

Subtask: 4, 6

Verdict:

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

correct output
2

user output
(empty)

Test 47

Subtask: 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 48

Subtask: 4, 6

Verdict:

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

correct output
2

user output
(empty)

Test 49

Subtask: 4, 6

Verdict:

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

correct output
2

user output
(empty)

Test 50

Subtask: 4, 6

Verdict:

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

correct output
0

user output
(empty)

Test 51

Subtask: 5, 6

Verdict:

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

correct output
97138096

user output
(empty)

Test 52

Subtask: 5, 6

Verdict:

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

correct output
841074570

user output
(empty)

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
(empty)

Test 55

Subtask: 5, 6

Verdict:

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

correct output
970435703

user output
(empty)

Test 56

Subtask: 5, 6

Verdict:

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

correct output
27240937

user output
(empty)

Test 57

Subtask: 6

Verdict:

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

correct output
980044634

user output
(empty)

Test 58

Subtask: 6

Verdict:

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

correct output
883528742

user output
(empty)

Test 59

Subtask: 6

Verdict:

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

correct output
79062217

user output
(empty)

Test 60

Subtask: 6

Verdict:

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

correct output
864991067

user output
(empty)

Test 61

Subtask: 6

Verdict:

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

correct output
471882140

user output
(empty)

Test 62

Subtask: 6

Verdict:

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

correct output
235428850

user output
(empty)