CSES - Datatähti 2026 loppu

Submission details
Task:	Polut
Sender:	Verlet
Submission time:	2026-01-17 16:50:30 +0200
Language:	C++ (C++20)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	9
#2	ACCEPTED	19
#3	ACCEPTED	22
#4	ACCEPTED	18
#5	ACCEPTED	32

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 3, 4, 5	details
#2	ACCEPTED	0.01 s	1, 4, 5	details
#3	ACCEPTED	0.01 s	1, 4, 5	details
#4	ACCEPTED	0.01 s	1, 4, 5	details
#5	ACCEPTED	0.21 s	2, 5	details
#6	ACCEPTED	0.23 s	2, 5	details
#7	ACCEPTED	0.01 s	2, 4, 5	details
#8	ACCEPTED	0.22 s	3, 5	details
#9	ACCEPTED	0.22 s	3, 5	details
#10	ACCEPTED	0.01 s	3, 4, 5	details
#11	ACCEPTED	0.02 s	4, 5	details
#12	ACCEPTED	0.02 s	4, 5	details
#13	ACCEPTED	0.25 s	5	details
#14	ACCEPTED	0.31 s	5	details
#15	ACCEPTED	0.02 s	4, 5	details
#16	ACCEPTED	0.01 s	1, 4, 5	details

Code

#include <iostream>
#include <vector>
#include <queue>
 
#define S 1000001
#define M 1000000007
 
#define pb push_back
 
using namespace std;
 
using ll = long long;
 
vector<int> adj[S];
 
// Find shortest paths
int v[S];
int dist[S];
 
void bfs(int r)
{
    queue<pair<int, int>> q;
 
    q.push({r, 0}); v[r] = 1;
 
    while (!q.empty())
    {
        auto [n, d] = q.front(); q.pop();
 
        dist[n] = d;
 
        for (int c : adj[n])
        {
            if (!v[c])
            {
                q.push({c, d + 1}); v[c] = 1;
            }
        }
    }
}
 
ll dp[S][10];
 
int c = 0;
// node, remaining distance, target
ll solve(int n, int d, int t)
{
    c++;
    // target is unreachable
    if (d < dist[n])
        return 0;
    
    // target reached
    if (d == 0 && n == t)
        return 1;
    
    int extra = d - dist[n];
 
    if (dp[n][extra] != -1)
        return dp[n][extra];
    
    // explore children
    ll s = 0;
    for (int c : adj[n])
    {
        s = (s + solve(c, d - 1, t)) % M;
    }
 
    return dp[n][extra] = s;
}
 
 
int main()
{
    int n, m, p; cin >> n >> m >> p;
 
    for (int i = 1; i <= n; i++)
        for (ll & v : dp[i])
            v = -1;
 
    for (int i = 0; i < m; i++)
    {
        int a, b; cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
 
    bfs(n);
 
    for (int i = 0; i < p; i++)
    {
        cout << solve(1, dist[1] + i, n) % M << " ";
    }
    cout << endl;
 
    // cout << c << endl;
}

Test details

Test 1 (public)

Group: 1, 3, 4, 5

Verdict: ACCEPTED

input
`4 5 3 1 2 1 3 2 3 2 4 ...` view save

correct output
`2 2 10` view save

user output
`2 2 10` view save

Test 2

Group: 1, 4, 5

Verdict: ACCEPTED

input
`2 1 1 2 1` view save

correct output
`1` view save

user output
`1` view save

Test 3

Group: 1, 4, 5

Verdict: ACCEPTED

input
`10 20 10 6 10 8 1 4 6 9 1 ...` view save

correct output
`2 5 34 123 611 2503 11415 4882...` view save

user output
`2 5 34 123 611 2503 11415 4882...` view save

Test 4

Group: 1, 4, 5

Verdict: ACCEPTED

input
`10 20 10 4 10 2 3 8 4 7 8 ...` view save

correct output
`1 7 26 140 509 2483 9454 43570...` view save

user output
`1 7 26 140 509 2483 9454 43570...` view save

Test 5

Group: 2, 5

Verdict: ACCEPTED

input
`100000 200000 2 96303 53915 64836 4748 6389 40954 60420 91374 ...` view save

correct output
`1 0` view save

user output
`1 0` view save

Test 6

Group: 2, 5

Verdict: ACCEPTED

input
`100000 200000 2 72817 17293 93269 856 51497 26888 41679 96276 ...` view save

correct output
`5 8` view save

user output
`5 8` view save

Test 7

Group: 2, 4, 5

Verdict: ACCEPTED

input
`474 517 2 1 2 1 3 2 4 3 4 ...` view save

correct output
`0 0` view save

user output
`0 0` view save

Test 8

Group: 3, 5

Verdict: ACCEPTED

input
`100000 200000 3 59846 53439 11468 57874 83443 13914 46177 15147 ...` view save

correct output
`1 0 32` view save

user output
`1 0 32` view save

Test 9

Group: 3, 5

Verdict: ACCEPTED

input
`100000 200000 3 23665 7205 83252 56604 14852 7299 2836 9864 ...` view save

correct output
`1 0 33` view save

user output
`1 0 33` view save

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

input
`474 517 3 1 2 1 3 2 4 3 4 ...` view save

correct output
`0 0 986681410` view save

user output
`0 0 986681410` view save

Test 11

Group: 4, 5

Verdict: ACCEPTED

input
`1000 2000 10 691 424 80 318 681 539 33 342 ...` view save

correct output
`1 6 39 252 1242 7715 36269 212...` view save

user output
`1 6 39 252 1242 7715 36269 212...` view save

Test 12

Group: 4, 5

Verdict: ACCEPTED

input
`1000 2000 10 979 324 770 562 560 7 169 738 ...` view save

correct output
`2 2 81 150 2435 6460 66843 223...` view save

user output
`2 2 81 150 2435 6460 66843 223...` view save

Test 13

Group: 5

Verdict: ACCEPTED

input
`100000 200000 10 54544 86042 14060 20746 47891 4317 76648 84193 ...` view save

correct output
`1 3 54 169 1917 6237 56922 192...` view save

user output
`1 3 54 169 1917 6237 56922 192...` view save

Test 14

Group: 5

Verdict: ACCEPTED

input
`100000 200000 10 73275 88704 74521 54506 51906 57193 29561 44568 ...` view save

correct output
`6 19 338 1212 12462 49357 3873...` view save

user output
`6 19 338 1212 12462 49357 3873...` view save

Test 15

Group: 4, 5

Verdict: ACCEPTED

input
`1000 1989 10 822 821 979 989 138 139 968 981 ...` view save

correct output
`1 44 2935 131120 6357888 28564...` view save

user output
`1 44 2935 131120 6357888 28564...` view save

Test 16

Group: 1, 4, 5

Verdict: ACCEPTED

input
`3 3 1 1 2 1 3 2 3` view save

correct output
`1` view save

user output
`1` view save

Datatähti 2026 loppu

Polut

Code

Test details

Test 1 (public)

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Tasks

Submissions (Verlet)