Submission #914932

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
914932	2024-01-23T00:53:36 Z	SchillingW	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1046 ms	100244 KB

tracks

#include <iostream>
#include <queue>

int main() {

    int N, M;
    std::cin >> N >> M;
    char g[N * M];
    for (int i = 0; i < N * M; i++) std::cin >> g[i];

    int D[4] {-1, -M, 1, M};

    int d[N * M];
    std::fill(d, d + N * M, -1);
    std::queue<int> q, pq;

    q.push(0);
    d[0] = 1;
    while (!q.empty() || !pq.empty()) {

        int p;
        if (!pq.empty()) p = pq.front(), pq.pop();
        else p = q.front(), q.pop();

        for (int i : D) {
            if (p + i >= 0 && p + i < N * M && !(i == -1 && p % M == 0) && !(i == 1 && p % M == M - 1)) {
                if (g[p + i] != '.' && d[p + i] == -1) {

                    if (g[p] == g[p + i]) pq.push(p + i), d[p + i] = d[p];
                    else q.push(p + i), d[p + i] = d[p] + 1;
                }
            }
        }
    }

    int w = 0;
    for (int i = 0; i < N * M; i++) if (d[i] > w) w = d[i];

    std::cout << w << "\n";
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	1628 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	9 ms	1244 KB	Output is correct
5	Correct	4 ms	860 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	4 ms	812 KB	Output is correct
11	Correct	3 ms	604 KB	Output is correct
12	Correct	6 ms	860 KB	Output is correct
13	Correct	4 ms	860 KB	Output is correct
14	Correct	4 ms	860 KB	Output is correct
15	Correct	15 ms	1920 KB	Output is correct
16	Correct	15 ms	1624 KB	Output is correct
17	Correct	13 ms	1628 KB	Output is correct
18	Correct	9 ms	1372 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	604 KB	Output is correct
2	Correct	75 ms	9484 KB	Output is correct
3	Correct	655 ms	94272 KB	Output is correct
4	Correct	189 ms	22352 KB	Output is correct
5	Correct	379 ms	53232 KB	Output is correct
6	Correct	998 ms	100244 KB	Output is correct
7	Correct	3 ms	600 KB	Output is correct
8	Correct	2 ms	604 KB	Output is correct
9	Correct	3 ms	604 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	75 ms	9588 KB	Output is correct
14	Correct	43 ms	5520 KB	Output is correct
15	Correct	41 ms	6228 KB	Output is correct
16	Correct	33 ms	3984 KB	Output is correct
17	Correct	202 ms	24336 KB	Output is correct
18	Correct	167 ms	23892 KB	Output is correct
19	Correct	157 ms	22356 KB	Output is correct
20	Correct	146 ms	20564 KB	Output is correct
21	Correct	425 ms	54864 KB	Output is correct
22	Correct	388 ms	53100 KB	Output is correct
23	Correct	389 ms	45652 KB	Output is correct
24	Correct	390 ms	53700 KB	Output is correct
25	Correct	825 ms	94548 KB	Output is correct
26	Correct	731 ms	72280 KB	Output is correct
27	Correct	935 ms	95176 KB	Output is correct
28	Correct	1046 ms	99728 KB	Output is correct
29	Correct	1044 ms	99372 KB	Output is correct
30	Correct	918 ms	97140 KB	Output is correct
31	Correct	673 ms	60868 KB	Output is correct
32	Correct	858 ms	95180 KB	Output is correct