답안 #867727

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
867727	2023-10-29T10:24:06 Z	BoopyTheNoob	Tracks in the Snow (BOI13_tracks)	C++14	40.2083 / 100	2000 ms	758216 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

#	결과	실행 시간	메모리	Grader output
1	Correct	64 ms	64336 KB	Output is correct
2	Incorrect	30 ms	63068 KB	Output isn't correct
3	Incorrect	30 ms	63068 KB	Output isn't correct
4	Correct	49 ms	66376 KB	Output is correct
5	Incorrect	32 ms	63060 KB	Output isn't correct
6	Incorrect	31 ms	63028 KB	Output isn't correct
7	Incorrect	30 ms	63060 KB	Output isn't correct
8	Correct	32 ms	63192 KB	Output is correct
9	Correct	32 ms	63108 KB	Output is correct
10	Correct	32 ms	63056 KB	Output is correct
11	Correct	37 ms	63924 KB	Output is correct
12	Correct	43 ms	63832 KB	Output is correct
13	Incorrect	32 ms	63068 KB	Output isn't correct
14	Incorrect	32 ms	63068 KB	Output isn't correct
15	Correct	57 ms	63872 KB	Output is correct
16	Correct	71 ms	64576 KB	Output is correct
17	Correct	46 ms	63580 KB	Output is correct
18	Correct	48 ms	66272 KB	Output is correct

Subtask #2

21.875 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	63068 KB	Output is correct
2	Incorrect	110 ms	64840 KB	Output isn't correct
3	Incorrect	57 ms	80836 KB	Output isn't correct
4	Correct	98 ms	67184 KB	Output is correct
5	Correct	210 ms	72796 KB	Output is correct
6	Execution timed out	2051 ms	296628 KB	Time limit exceeded
7	Incorrect	31 ms	63192 KB	Output isn't correct
8	Correct	31 ms	63056 KB	Output is correct
9	Incorrect	34 ms	63012 KB	Output isn't correct
10	Incorrect	30 ms	63060 KB	Output isn't correct
11	Correct	31 ms	63060 KB	Output is correct
12	Incorrect	30 ms	63064 KB	Output isn't correct
13	Incorrect	126 ms	65060 KB	Output isn't correct
14	Incorrect	73 ms	64316 KB	Output isn't correct
15	Correct	44 ms	64224 KB	Output is correct
16	Incorrect	77 ms	64080 KB	Output isn't correct
17	Incorrect	36 ms	67412 KB	Output isn't correct
18	Correct	111 ms	67420 KB	Output is correct
19	Correct	96 ms	67208 KB	Output is correct
20	Incorrect	36 ms	66644 KB	Output isn't correct
21	Incorrect	52 ms	73296 KB	Output isn't correct
22	Correct	250 ms	72788 KB	Output is correct
23	Incorrect	443 ms	72016 KB	Output isn't correct
24	Incorrect	45 ms	72796 KB	Output isn't correct
25	Incorrect	59 ms	80724 KB	Output isn't correct
26	Execution timed out	2098 ms	758216 KB	Time limit exceeded
27	Execution timed out	2044 ms	383076 KB	Time limit exceeded
28	Execution timed out	2065 ms	298264 KB	Time limit exceeded
29	Execution timed out	2079 ms	279080 KB	Time limit exceeded
30	Execution timed out	2075 ms	329716 KB	Time limit exceeded
31	Correct	1795 ms	82136 KB	Output is correct
32	Execution timed out	2057 ms	349768 KB	Time limit exceeded