Submission #159012

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
159012	2019-10-20T05:55:09 Z	FutymyClone	Tracks in the Snow (BOI13_tracks)	C++14	91.25 / 100	1423 ms	1048580 KB

tracks

#include <bits/stdc++.h>

using namespace std;

const int N = 4005;

int n, m, ans = 0;
bool visited[N][N];
char a[N][N];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};

bool ok (int x, int y) {
    return (x >= 1 && x <= n && y >= 1 && y <= m && !visited[x][y] && a[x][y] != '.');
}

void bfs (queue <pair <int, int> > q1, queue <pair <int, int> > q2) {
    if (q1.empty()) return;
    ans++;
    while (!q1.empty()) {
        int x = q1.front().first, y = q1.front().second; q1.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (!ok(nx, ny)) continue;
            visited[nx][ny] = true;
            if (a[nx][ny] == a[x][y]) q1.push({nx, ny});
            else q2.push({nx, ny});
        }
    }

    bfs(q2, q1);
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    queue <pair <int, int> > q1, q2;
    q1.push({1, 1});
    visited[1][1] = true;
    bfs(q1, q2);
    cout << ans;
    return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	5496 KB	Output is correct
2	Correct	2 ms	760 KB	Output is correct
3	Correct	3 ms	760 KB	Output is correct
4	Correct	14 ms	4600 KB	Output is correct
5	Correct	7 ms	2808 KB	Output is correct
6	Correct	2 ms	760 KB	Output is correct
7	Correct	3 ms	760 KB	Output is correct
8	Correct	3 ms	888 KB	Output is correct
9	Correct	3 ms	1144 KB	Output is correct
10	Correct	6 ms	2552 KB	Output is correct
11	Correct	5 ms	2040 KB	Output is correct
12	Correct	10 ms	3064 KB	Output is correct
13	Correct	7 ms	2924 KB	Output is correct
14	Correct	7 ms	2936 KB	Output is correct
15	Correct	20 ms	5404 KB	Output is correct
16	Correct	21 ms	5496 KB	Output is correct
17	Correct	17 ms	4856 KB	Output is correct
18	Correct	14 ms	4600 KB	Output is correct

Subtask #2

61.25 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	37716 KB	Output is correct
2	Correct	82 ms	15488 KB	Output is correct
3	Correct	1423 ms	886020 KB	Output is correct
4	Correct	122 ms	22060 KB	Output is correct
5	Runtime error	1092 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
6	Correct	1080 ms	64392 KB	Output is correct
7	Correct	40 ms	38008 KB	Output is correct
8	Correct	39 ms	37624 KB	Output is correct
9	Correct	5 ms	888 KB	Output is correct
10	Correct	6 ms	4088 KB	Output is correct
11	Correct	36 ms	34168 KB	Output is correct
12	Correct	19 ms	17400 KB	Output is correct
13	Correct	82 ms	15480 KB	Output is correct
14	Correct	47 ms	10796 KB	Output is correct
15	Correct	262 ms	214268 KB	Output is correct
16	Correct	37 ms	6648 KB	Output is correct
17	Correct	211 ms	31840 KB	Output is correct
18	Correct	980 ms	813568 KB	Output is correct
19	Correct	122 ms	22068 KB	Output is correct
20	Correct	288 ms	190968 KB	Output is correct
21	Correct	749 ms	508116 KB	Output is correct
22	Runtime error	1054 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
23	Correct	407 ms	48248 KB	Output is correct
24	Runtime error	1109 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
25	Runtime error	1257 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
26	Correct	684 ms	35524 KB	Output is correct
27	Correct	941 ms	42988 KB	Output is correct
28	Correct	1136 ms	65260 KB	Output is correct
29	Correct	1132 ms	64148 KB	Output is correct
30	Correct	927 ms	58372 KB	Output is correct
31	Correct	870 ms	78648 KB	Output is correct
32	Correct	784 ms	42048 KB	Output is correct