Submission #867716

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
867716	2023-10-29T10:04:33 Z	BoopyTheNoob	Tracks in the Snow (BOI13_tracks)	C++14	84.6875 / 100	2000 ms	755100 KB

tracks

#include <bits/stdc++.h>
using namespace std;

int main (void) {
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int N, M;
    cin >> N >> M;
    vector<string> grid(N);
    for (int i = 0; i < N; i++)
        cin >> grid[i];
    vector<vector<int>> dist(N, vector<int>(M, 1e9));
    deque<vector<int>> bfs;
    bfs.push_back({0, 0, 1});
    int ans = 0;
    while (!bfs.empty()) {
        int x = bfs.front()[0], y = bfs.front()[1], d = bfs.front()[2];
        bfs.pop_front();
        dist[x][y] = d;
        ans = max(ans, d);
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M)
                continue;
            if (dist[nx][ny] < 1e9 || grid[nx][ny] == '.')
                continue;
            vector<int> next = {nx, ny, d};
            if (grid[x][y] != grid[nx][ny]) {
                next[2]++;
                bfs.push_back(next);
            } else
                bfs.push_front(next);
        }
    }
    /*for (auto x: dist) {
        for (auto y: x) {
            cout << y << " ";
        }
        cout << endl;
    }*/
    cout << ans << endl;
    return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	3164 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	21 ms	4444 KB	Output is correct
5	Correct	4 ms	860 KB	Output is correct
6	Correct	0 ms	432 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	4 ms	860 KB	Output is correct
11	Correct	6 ms	1372 KB	Output is correct
12	Correct	14 ms	1596 KB	Output is correct
13	Correct	4 ms	860 KB	Output is correct
14	Correct	4 ms	860 KB	Output is correct
15	Correct	28 ms	2392 KB	Output is correct
16	Correct	38 ms	3164 KB	Output is correct
17	Correct	17 ms	2136 KB	Output is correct
18	Correct	22 ms	4504 KB	Output is correct

Subtask #2

54.6875 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	860 KB	Output is correct
2	Correct	100 ms	10564 KB	Output is correct
3	Correct	574 ms	109184 KB	Output is correct
4	Correct	122 ms	25976 KB	Output is correct
5	Correct	300 ms	55892 KB	Output is correct
6	Execution timed out	2035 ms	324648 KB	Time limit exceeded
7	Correct	2 ms	856 KB	Output is correct
8	Correct	2 ms	860 KB	Output is correct
9	Correct	5 ms	1116 KB	Output is correct
10	Correct	1 ms	600 KB	Output is correct
11	Correct	2 ms	860 KB	Output is correct
12	Correct	2 ms	452 KB	Output is correct
13	Correct	106 ms	10756 KB	Output is correct
14	Correct	60 ms	6792 KB	Output is correct
15	Correct	29 ms	7256 KB	Output is correct
16	Correct	57 ms	4584 KB	Output is correct
17	Correct	284 ms	28240 KB	Output is correct
18	Correct	131 ms	27676 KB	Output is correct
19	Correct	134 ms	25944 KB	Output is correct
20	Correct	131 ms	23996 KB	Output is correct
21	Correct	326 ms	57816 KB	Output is correct
22	Correct	296 ms	55892 KB	Output is correct
23	Correct	515 ms	48580 KB	Output is correct
24	Correct	265 ms	56840 KB	Output is correct
25	Correct	595 ms	108576 KB	Output is correct
26	Execution timed out	2092 ms	755100 KB	Time limit exceeded
27	Execution timed out	2081 ms	409792 KB	Time limit exceeded
28	Execution timed out	2106 ms	326616 KB	Time limit exceeded
29	Execution timed out	2053 ms	307672 KB	Time limit exceeded
30	Execution timed out	2053 ms	356216 KB	Time limit exceeded
31	Correct	1867 ms	70740 KB	Output is correct
32	Execution timed out	2067 ms	377868 KB	Time limit exceeded