Submission #867730

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

tracks

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

int dist[4000][4000];

int main (void) {
    iostream::sync_with_stdio(false);
	cin.tie(0);
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int N, M;
    cin >> N >> M;
    //vector<string> grid(N);
    string grid[4000];
    for (int i = 0; i < N; i++)
        cin >> grid[i];
    //vector<vector<int>> dist(N, vector<int>(M, 0));
    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] != 0 || 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	35 ms	4692 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	19 ms	6320 KB	Output is correct
5	Correct	3 ms	2140 KB	Output is correct
6	Correct	0 ms	604 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Correct	1 ms	860 KB	Output is correct
9	Correct	1 ms	860 KB	Output is correct
10	Correct	4 ms	1628 KB	Output is correct
11	Correct	7 ms	2396 KB	Output is correct
12	Correct	15 ms	2612 KB	Output is correct
13	Correct	3 ms	2140 KB	Output is correct
14	Correct	3 ms	2140 KB	Output is correct
15	Correct	26 ms	3808 KB	Output is correct
16	Correct	35 ms	4700 KB	Output is correct
17	Correct	15 ms	3676 KB	Output is correct
18	Correct	19 ms	6236 KB	Output is correct

Subtask #2

54.6875 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	15960 KB	Output is correct
2	Correct	86 ms	10588 KB	Output is correct
3	Correct	335 ms	60024 KB	Output is correct
4	Correct	71 ms	25680 KB	Output is correct
5	Correct	210 ms	42420 KB	Output is correct
6	Execution timed out	2035 ms	296760 KB	Time limit exceeded
7	Correct	7 ms	16472 KB	Output is correct
8	Correct	9 ms	15960 KB	Output is correct
9	Correct	4 ms	1116 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	7 ms	16220 KB	Output is correct
12	Correct	1 ms	1116 KB	Output is correct
13	Correct	81 ms	10688 KB	Output is correct
14	Correct	55 ms	7212 KB	Output is correct
15	Correct	25 ms	9308 KB	Output is correct
16	Correct	45 ms	4472 KB	Output is correct
17	Correct	204 ms	21588 KB	Output is correct
18	Correct	80 ms	28244 KB	Output is correct
19	Correct	72 ms	25792 KB	Output is correct
20	Correct	88 ms	19024 KB	Output is correct
21	Correct	209 ms	41552 KB	Output is correct
22	Correct	213 ms	42576 KB	Output is correct
23	Correct	430 ms	35416 KB	Output is correct
24	Correct	156 ms	38572 KB	Output is correct
25	Correct	396 ms	80668 KB	Output is correct
26	Execution timed out	2067 ms	750476 KB	Time limit exceeded
27	Execution timed out	2062 ms	382912 KB	Time limit exceeded
28	Execution timed out	2036 ms	296284 KB	Time limit exceeded
29	Execution timed out	2054 ms	279304 KB	Time limit exceeded
30	Execution timed out	2078 ms	328532 KB	Time limit exceeded
31	Correct	1780 ms	69440 KB	Output is correct
32	Execution timed out	2019 ms	349820 KB	Time limit exceeded