Submission #159013

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
159013	2019-10-20T05:56:51 Z	FutymyClone	Tracks in the Snow (BOI13_tracks)	C++14	45.1042 / 100	1242 ms	1048580 KB

tracks

#include <bits/stdc++.h>

using namespace std;

const int N = 4005;

int n, m, ans = 0;
bool visited[N][N];
string a[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++) cin >> a[i];
    queue <pair <int, int> > q1, q2;
    q1.push({1, 1});
    visited[1][1] = true;
    bfs(q1, q2);
    cout << ans;
    return 0;
}

Subtask #1

16.6666666667 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	22 ms	4088 KB	Output isn't correct
2	Incorrect	3 ms	760 KB	Output isn't correct
3	Correct	3 ms	760 KB	Output is correct
4	Correct	13 ms	3064 KB	Output is correct
5	Correct	6 ms	1912 KB	Output is correct
6	Incorrect	3 ms	760 KB	Output isn't correct
7	Correct	4 ms	760 KB	Output is correct
8	Incorrect	3 ms	760 KB	Output isn't correct
9	Correct	3 ms	888 KB	Output is correct
10	Correct	5 ms	1912 KB	Output is correct
11	Incorrect	5 ms	1528 KB	Output isn't correct
12	Incorrect	9 ms	2168 KB	Output isn't correct
13	Correct	5 ms	1884 KB	Output is correct
14	Correct	5 ms	1960 KB	Output is correct
15	Correct	18 ms	3832 KB	Output is correct
16	Incorrect	22 ms	3960 KB	Output isn't correct
17	Incorrect	15 ms	3448 KB	Output isn't correct
18	Correct	12 ms	3064 KB	Output is correct

Subtask #2

28.4375 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	504 KB	Output isn't correct
2	Incorrect	67 ms	13680 KB	Output isn't correct
3	Correct	1242 ms	890424 KB	Output is correct
4	Correct	79 ms	18424 KB	Output is correct
5	Incorrect	29 ms	18984 KB	Output isn't correct
6	Correct	1057 ms	60156 KB	Output is correct
7	Incorrect	22 ms	16248 KB	Output isn't correct
8	Incorrect	2 ms	524 KB	Output isn't correct
9	Correct	4 ms	1144 KB	Output is correct
10	Correct	6 ms	4180 KB	Output is correct
11	Incorrect	2 ms	508 KB	Output isn't correct
12	Correct	19 ms	16888 KB	Output is correct
13	Incorrect	67 ms	13604 KB	Output isn't correct
14	Incorrect	44 ms	9592 KB	Output isn't correct
15	Incorrect	5 ms	2424 KB	Output isn't correct
16	Correct	35 ms	5880 KB	Output is correct
17	Correct	179 ms	26844 KB	Output is correct
18	Incorrect	16 ms	7160 KB	Output isn't correct
19	Correct	84 ms	17656 KB	Output is correct
20	Correct	267 ms	186924 KB	Output is correct
21	Incorrect	692 ms	500532 KB	Output isn't correct
22	Incorrect	29 ms	18936 KB	Output isn't correct
23	Incorrect	352 ms	39324 KB	Output isn't correct
24	Incorrect	68 ms	54264 KB	Output isn't correct
25	Runtime error	1058 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
26	Incorrect	600 ms	27704 KB	Output isn't correct
27	Correct	812 ms	37188 KB	Output is correct
28	Correct	1061 ms	59236 KB	Output is correct
29	Incorrect	1016 ms	58380 KB	Output isn't correct
30	Correct	898 ms	53136 KB	Output is correct
31	Incorrect	908 ms	68236 KB	Output isn't correct
32	Incorrect	685 ms	36128 KB	Output isn't correct