CSES - Datatähti 2026 loppu

Submission details
Task:	Polut
Sender:	Verlet
Submission time:	2026-01-17 16:34:57 +0200
Language:	C++ (C++20)
Status:	READY
Result:	9

Feedback
group	verdict	score
#1	ACCEPTED	9
#2	WRONG ANSWER	0
#3	WRONG ANSWER	0
#4	WRONG ANSWER	0
#5	WRONG ANSWER	0

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.22 s	2, 5	details
#6	ACCEPTED	0.22 s	2, 5	details
#7	WRONG ANSWER	0.02 s	2, 4, 5	details
#8	ACCEPTED	0.23 s	3, 5	details
#9	ACCEPTED	0.22 s	3, 5	details
#10	WRONG ANSWER	0.02 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.28 s	5	details
#15	WRONG ANSWER	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 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 += solve(c, d - 1, t);
    }

    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) << " ";
    }
    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: WRONG ANSWER

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

correct output
`0 0` view save

user output
`1000000007 0` view save

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

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: WRONG ANSWER

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

correct output
`0 0 986681410` view save

user output
`1000000007 0 145986682425` view save

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

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: WRONG ANSWER

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

Feedback: Incorrect character on line 1 col 36: expected "888762", got "13000888853"

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)