| Task: | Polut |
| Sender: | aatukaj |
| Submission time: | 2026-01-17 13:58:04 +0200 |
| Language: | C++ (C++17) |
| Status: | READY |
| Result: | 100 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 9 |
| #2 | ACCEPTED | 19 |
| #3 | ACCEPTED | 22 |
| #4 | ACCEPTED | 18 |
| #5 | ACCEPTED | 32 |
| 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.14 s | 2, 5 | details |
| #6 | ACCEPTED | 0.14 s | 2, 5 | details |
| #7 | ACCEPTED | 0.01 s | 2, 4, 5 | details |
| #8 | ACCEPTED | 0.16 s | 3, 5 | details |
| #9 | ACCEPTED | 0.16 s | 3, 5 | details |
| #10 | ACCEPTED | 0.01 s | 3, 4, 5 | details |
| #11 | ACCEPTED | 0.01 s | 4, 5 | details |
| #12 | ACCEPTED | 0.01 s | 4, 5 | details |
| #13 | ACCEPTED | 0.30 s | 5 | details |
| #14 | ACCEPTED | 0.30 s | 5 | details |
| #15 | ACCEPTED | 0.01 s | 4, 5 | details |
| #16 | ACCEPTED | 0.01 s | 1, 4, 5 | details |
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
// shortest path dag
using ll = long long;
const int mxN = 1e5;
int dist[mxN];
ll dp[11][mxN];
vector<int> adj[mxN];
int n, m, p;
void bfs() {
queue<int> q;
q.push(n-1);
for (int i=0; i<n; i++) dist[i] = -1;
dist[n-1] = 0;
while (q.size()) {
int v= q.front(); q.pop();
for (auto u: adj[v]) {
if (dist[u]==-1) {
dist[u] = dist[v]+1;
q.push(u);
};
};
};
};
bool vis[mxN];
vector<int> ord;
void dfs(int v, int k) {
vis[v] = true;
if (v==n-1 && k==0) {
dp[0][v] = 1;
return;
}
for (auto u: adj[v]) {
if (dist[v]==dist[u]+1) {
if (!vis[u]) dfs(u, k);
dp[k][v] += dp[k][u];
}
else if (dist[v]==dist[u]) {
if (k>=1) dp[k][v] += dp[k-1][u];
} else {
if (k>=2) dp[k][v] += dp[k-2][u];
};
dp[k][v] %= MOD;
};
};
void $() {
cin >> n >> m >> p;
for (int i=0; i<m; i++) {
int u, v;
cin >> u >> v;
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
};
bfs();
for (int k=0; k<p; k++) {
memset(vis, 0, sizeof vis);
for (int i=0; i<n; i++) if (!vis[i]) dfs(i, k);
}
for (int k=0; k<p; k++) cout << dp[k][0] << ' ';
cout << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
$();
}
Test details
Test 1 (public)
Group: 1, 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 4 5 3 1 2 1 3 2 3 2 4 ... |
| correct output |
|---|
| 2 2 10 |
| user output |
|---|
| 2 2 10 |
Test 2
Group: 1, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 1 1 2 1 |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |
Test 3
Group: 1, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 10 20 10 6 10 8 1 4 6 9 1 ... |
| correct output |
|---|
| 2 5 34 123 611 2503 11415 4882... |
| user output |
|---|
| 2 5 34 123 611 2503 11415 4882... |
Test 4
Group: 1, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 10 20 10 4 10 2 3 8 4 7 8 ... |
| correct output |
|---|
| 1 7 26 140 509 2483 9454 43570... |
| user output |
|---|
| 1 7 26 140 509 2483 9454 43570... |
Test 5
Group: 2, 5
Verdict: ACCEPTED
| input |
|---|
| 100000 200000 2 96303 53915 64836 4748 6389 40954 60420 91374 ... |
| correct output |
|---|
| 1 0 |
| user output |
|---|
| 1 0 |
Test 6
Group: 2, 5
Verdict: ACCEPTED
| input |
|---|
| 100000 200000 2 72817 17293 93269 856 51497 26888 41679 96276 ... |
| correct output |
|---|
| 5 8 |
| user output |
|---|
| 5 8 |
Test 7
Group: 2, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 474 517 2 1 2 1 3 2 4 3 4 ... |
| correct output |
|---|
| 0 0 |
| user output |
|---|
| 0 0 |
Test 8
Group: 3, 5
Verdict: ACCEPTED
| input |
|---|
| 100000 200000 3 59846 53439 11468 57874 83443 13914 46177 15147 ... |
| correct output |
|---|
| 1 0 32 |
| user output |
|---|
| 1 0 32 |
Test 9
Group: 3, 5
Verdict: ACCEPTED
| input |
|---|
| 100000 200000 3 23665 7205 83252 56604 14852 7299 2836 9864 ... |
| correct output |
|---|
| 1 0 33 |
| user output |
|---|
| 1 0 33 |
Test 10
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 474 517 3 1 2 1 3 2 4 3 4 ... |
| correct output |
|---|
| 0 0 986681410 |
| user output |
|---|
| 0 0 986681410 |
Test 11
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1000 2000 10 691 424 80 318 681 539 33 342 ... |
| correct output |
|---|
| 1 6 39 252 1242 7715 36269 212... |
| user output |
|---|
| 1 6 39 252 1242 7715 36269 212... |
Test 12
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1000 2000 10 979 324 770 562 560 7 169 738 ... |
| correct output |
|---|
| 2 2 81 150 2435 6460 66843 223... |
| user output |
|---|
| 2 2 81 150 2435 6460 66843 223... |
Test 13
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 100000 200000 10 54544 86042 14060 20746 47891 4317 76648 84193 ... |
| correct output |
|---|
| 1 3 54 169 1917 6237 56922 192... |
| user output |
|---|
| 1 3 54 169 1917 6237 56922 192... |
Test 14
Group: 5
Verdict: ACCEPTED
| input |
|---|
| 100000 200000 10 73275 88704 74521 54506 51906 57193 29561 44568 ... |
| correct output |
|---|
| 6 19 338 1212 12462 49357 3873... |
| user output |
|---|
| 6 19 338 1212 12462 49357 3873... |
Test 15
Group: 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1000 1989 10 822 821 979 989 138 139 968 981 ... |
| correct output |
|---|
| 1 44 2935 131120 6357888 28564... |
| user output |
|---|
| 1 44 2935 131120 6357888 28564... |
Test 16
Group: 1, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 3 3 1 1 2 1 3 2 3 |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |