Submission #867720

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
867720	2023-10-29T10:13:49 Z	BoopyTheNoob	Tracks in the Snow (BOI13_tracks)	C++14	40.2083 / 100	2000 ms	758168 KB

tracks

#include <iostream>
#include <vector>
#include <deque>
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<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

18.3333333333 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	64560 KB	Output is correct
2	Incorrect	29 ms	63116 KB	Output isn't correct
3	Incorrect	30 ms	62972 KB	Output isn't correct
4	Correct	49 ms	66388 KB	Output is correct
5	Incorrect	31 ms	63056 KB	Output isn't correct
6	Incorrect	29 ms	63068 KB	Output isn't correct
7	Incorrect	29 ms	63060 KB	Output isn't correct
8	Correct	30 ms	63216 KB	Output is correct
9	Correct	30 ms	63016 KB	Output is correct
10	Correct	32 ms	63060 KB	Output is correct
11	Correct	34 ms	64092 KB	Output is correct
12	Correct	41 ms	63652 KB	Output is correct
13	Incorrect	32 ms	63176 KB	Output isn't correct
14	Incorrect	32 ms	63252 KB	Output isn't correct
15	Correct	53 ms	63868 KB	Output is correct
16	Correct	64 ms	64540 KB	Output is correct
17	Correct	43 ms	63568 KB	Output is correct
18	Correct	48 ms	66252 KB	Output is correct

Subtask #2

21.875 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	63068 KB	Output is correct
2	Incorrect	113 ms	65112 KB	Output isn't correct
3	Incorrect	58 ms	80672 KB	Output isn't correct
4	Correct	95 ms	67212 KB	Output is correct
5	Correct	213 ms	72788 KB	Output is correct
6	Execution timed out	2025 ms	298356 KB	Time limit exceeded
7	Incorrect	29 ms	63060 KB	Output isn't correct
8	Correct	30 ms	63060 KB	Output is correct
9	Incorrect	29 ms	63260 KB	Output isn't correct
10	Incorrect	33 ms	63064 KB	Output isn't correct
11	Correct	30 ms	63048 KB	Output is correct
12	Incorrect	29 ms	63064 KB	Output isn't correct
13	Incorrect	106 ms	64852 KB	Output isn't correct
14	Incorrect	79 ms	64080 KB	Output isn't correct
15	Correct	44 ms	64088 KB	Output is correct
16	Incorrect	72 ms	63952 KB	Output isn't correct
17	Incorrect	34 ms	67408 KB	Output isn't correct
18	Correct	93 ms	67420 KB	Output is correct
19	Correct	108 ms	67152 KB	Output is correct
20	Incorrect	34 ms	66652 KB	Output isn't correct
21	Incorrect	45 ms	73072 KB	Output isn't correct
22	Correct	209 ms	72904 KB	Output is correct
23	Incorrect	432 ms	72056 KB	Output isn't correct
24	Incorrect	47 ms	72784 KB	Output isn't correct
25	Incorrect	56 ms	80720 KB	Output isn't correct
26	Execution timed out	2095 ms	758168 KB	Time limit exceeded
27	Execution timed out	2090 ms	381296 KB	Time limit exceeded
28	Execution timed out	2035 ms	297064 KB	Time limit exceeded
29	Execution timed out	2045 ms	279536 KB	Time limit exceeded
30	Execution timed out	2079 ms	329620 KB	Time limit exceeded
31	Correct	1691 ms	82140 KB	Output is correct
32	Execution timed out	2069 ms	349672 KB	Time limit exceeded