Submission #867731

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
867731	2023-10-29T10:28:08 Z	BoopyTheNoob	Tracks in the Snow (BOI13_tracks)	C++14	97.8125 / 100	422 ms	126740 KB

tracks

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

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));
    int dist[4000][4000];
    deque<pair<int, int>> bfs;
    bfs.push_back({0, 0});
    dist[0][0] = 1;
    int ans = 0;
    while (!bfs.empty()) {
        int x = bfs.front().first, y = bfs.front().second;
        bfs.pop_front();
        ans = max(ans, dist[x][y]);
        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;
            pair<int, int> next = {nx, ny};
            if (grid[x][y] != grid[nx][ny]) {
                dist[nx][ny] = dist[x][y] + 1;
                bfs.push_back(next);
            } else {
                dist[nx][ny] = dist[x][y];
                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	63312 KB	Output is correct
2	Correct	29 ms	63068 KB	Output is correct
3	Correct	32 ms	63056 KB	Output is correct
4	Correct	32 ms	63324 KB	Output is correct
5	Correct	30 ms	63068 KB	Output is correct
6	Correct	29 ms	63068 KB	Output is correct
7	Correct	30 ms	63108 KB	Output is correct
8	Correct	33 ms	63064 KB	Output is correct
9	Correct	29 ms	63064 KB	Output is correct
10	Correct	31 ms	63060 KB	Output is correct
11	Correct	32 ms	63060 KB	Output is correct
12	Correct	31 ms	63324 KB	Output is correct
13	Correct	31 ms	63220 KB	Output is correct
14	Correct	30 ms	63156 KB	Output is correct
15	Correct	34 ms	63380 KB	Output is correct
16	Correct	38 ms	63324 KB	Output is correct
17	Correct	34 ms	63316 KB	Output is correct
18	Correct	35 ms	63576 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	63056 KB	Output is correct
2	Correct	53 ms	64828 KB	Output is correct
3	Correct	146 ms	80724 KB	Output is correct
4	Correct	67 ms	67084 KB	Output is correct
5	Correct	92 ms	72904 KB	Output is correct
6	Correct	386 ms	94156 KB	Output is correct
7	Correct	30 ms	63104 KB	Output is correct
8	Correct	34 ms	63060 KB	Output is correct
9	Correct	31 ms	63296 KB	Output is correct
10	Correct	31 ms	63068 KB	Output is correct
11	Correct	30 ms	63068 KB	Output is correct
12	Correct	35 ms	63060 KB	Output is correct
13	Correct	52 ms	64600 KB	Output is correct
14	Correct	42 ms	64080 KB	Output is correct
15	Correct	38 ms	64084 KB	Output is correct
16	Correct	40 ms	63784 KB	Output is correct
17	Correct	92 ms	67320 KB	Output is correct
18	Correct	61 ms	67404 KB	Output is correct
19	Correct	60 ms	67036 KB	Output is correct
20	Correct	57 ms	66644 KB	Output is correct
21	Correct	106 ms	73300 KB	Output is correct
22	Correct	92 ms	72904 KB	Output is correct
23	Correct	152 ms	71512 KB	Output is correct
24	Correct	95 ms	72944 KB	Output is correct
25	Incorrect	64 ms	80632 KB	Output isn't correct
26	Correct	377 ms	126740 KB	Output is correct
27	Correct	321 ms	99060 KB	Output is correct
28	Correct	405 ms	94216 KB	Output is correct
29	Correct	389 ms	91600 KB	Output is correct
30	Correct	422 ms	97640 KB	Output is correct
31	Correct	298 ms	74688 KB	Output is correct
32	Correct	370 ms	97580 KB	Output is correct