CSES - Datatähti 2025 loppu

Submission details
Task:	Suunnistus
Sender:	vgtcross
Submission time:	2025-01-18 14:40:14 +0200
Language:	C++ (C++20)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	31
#2	ACCEPTED	12
#3	ACCEPTED	57

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	3	details
#2	ACCEPTED	0.03 s	1, 2, 3	details
#3	ACCEPTED	0.03 s	1, 2, 3	details
#4	ACCEPTED	0.01 s	1, 2, 3	details
#5	ACCEPTED	0.01 s	1, 2, 3	details
#6	ACCEPTED	0.01 s	1, 2, 3	details
#7	ACCEPTED	0.24 s	2, 3	details
#8	ACCEPTED	0.26 s	2, 3	details
#9	ACCEPTED	0.01 s	2, 3	details
#10	ACCEPTED	0.42 s	3	details
#11	ACCEPTED	0.44 s	3	details
#12	ACCEPTED	0.05 s	3	details
#13	ACCEPTED	0.27 s	3	details
#14	ACCEPTED	0.04 s	2, 3	details
#15	ACCEPTED	0.01 s	3	details
#16	ACCEPTED	0.01 s	3	details
#17	ACCEPTED	0.03 s	2, 3	details

Code

#include <bits/stdc++.h>

#define debug(x) cout << #x << ": " << x << endl
#define fi first
#define se second
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int N = 505;

char g[N][N];
int dis[N][N];

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

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

    vector<vector<pii>> rd(k+2);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            char c;
            cin >> c;

            if (c == 'S') rd[0].push_back({i, j});
            else if (c == 'E') rd[k+1].push_back({i, j});
            else if ('1' <= c && c <= '9') rd[c-'0'].push_back({i, j});

            if (c != '#') c = '.';
            g[i][j] = c;
        }
    }

    memset(dis, 0, sizeof dis);
    dis[rd[0][0].fi][rd[0][0].se] = 1;
    for (int a = 0; a < k+1; ++a) {
        for (auto &p : rd[a]) {
            dis[p.fi][p.se] *= -1;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (dis[i][j] >= 0) dis[i][j] = 1e9;
            }
        }
        priority_queue<array<int, 3>> pq;
        for (auto &p : rd[a]) {
            pq.push({dis[p.fi][p.se], p.fi, p.se});
            dis[p.fi][p.se] *= -1;
        }

        while (pq.size()) {
            auto p = pq.top();
            pq.pop();
            if (dis[p[1]][p[2]] < -p[0]) continue;
            dis[p[1]][p[2]] = -p[0];
            for (int i = 0; i < 4; ++i) {
                int x = p[1] + dx[i];
                int y = p[2] + dy[i];
                if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.') {
                    if (dis[x][y] > -p[0] + 1) {
                        pq.push({p[0] - 1, x, y});
                        dis[x][y] = -p[0] + 1;
                    }
                }
            }
        }
    }

    int ans = dis[rd[k+1][0].fi][rd[k+1][0].se]-1;
    cout << (ans > 1e8 ? -1 : ans) << '\n';
}

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

    solve();
}

Test details

Test 1

Group: 3

Verdict: ACCEPTED

input
`10 10 9 S293#35616 #662963731 54975451#7 5162589168 ...` view save

correct output
`25` view save

user output
`25` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`500 500 0 .................................` view save

correct output
`301` view save

user output
`301` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`500 500 0 .#.........#.#..##..#............` view save

correct output
`253` view save

user output
`253` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`500 500 0 ...#......##.##.#.#..##..#..##...` view save

correct output
`-1` view save

user output
`-1` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`500 1 0 . . . . ...` view save

correct output
`77` view save

user output
`77` view save

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`1 500 0 .................................` view save

correct output
`166` view save

user output
`166` view save

Test 7

Group: 2, 3

Verdict: ACCEPTED

input
`500 500 9 .................................` view save

correct output
`3447` view save

user output
`3447` view save

Test 8

Group: 2, 3

Verdict: ACCEPTED

input
`500 500 9 .#........#..................#...` view save

correct output
`4952` view save

user output
`4952` view save

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
`500 500 9 ##.########.##########.#..#......` view save

correct output
`-1` view save

user output
`-1` view save

Test 10

Group: 3

Verdict: ACCEPTED

input
`500 500 9 623475428948841896621266296765...` view save

correct output
`205` view save

user output
`205` view save

Test 11

Group: 3

Verdict: ACCEPTED

input
`500 500 9 7##814125813#3463#272134469457...` view save

correct output
`157` view save

user output
`157` view save

Test 12

Group: 3

Verdict: ACCEPTED

input
`500 500 9 ##67##36##5#3###67###8972#61##...` view save

correct output
`-1` view save

user output
`-1` view save

Test 13

Group: 3

Verdict: ACCEPTED

input
`500 500 9 ....................#...#........` view save

correct output
`1313` view save

user output
`1313` view save

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
`499 499 9 S#...#...#...#...#...#...#...#...` view save

correct output
`1124942` view save

user output
`1124942` view save

Test 15

Group: 3

Verdict: ACCEPTED

input
`500 1 9 1 6 1 3 ...` view save

correct output
`332` view save

user output
`332` view save

Test 16

Group: 3

Verdict: ACCEPTED

input
`1 500 9 996327784392827829434482995353...` view save

correct output
`135` view save

user output
`135` view save

Test 17

Group: 2, 3

Verdict: ACCEPTED

input
`500 500 9 .................................` view save

correct output
`-1` view save

user output
`-1` view save

Datatähti 2025 loppu

Suunnistus

Code

Test details

Test 1

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

Test 17

Tasks

Submissions (vgtcross)