Submission #159014

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
159014	2019-10-20T05:57:51 Z	FutymyClone	Tracks in the Snow (BOI13_tracks)	C++14	91.25 / 100	1214 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], a[i] = "#" + 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

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	3704 KB	Output is correct
2	Correct	2 ms	760 KB	Output is correct
3	Correct	2 ms	760 KB	Output is correct
4	Correct	12 ms	2936 KB	Output is correct
5	Correct	5 ms	1912 KB	Output is correct
6	Correct	2 ms	760 KB	Output is correct
7	Correct	2 ms	760 KB	Output is correct
8	Correct	2 ms	760 KB	Output is correct
9	Correct	3 ms	888 KB	Output is correct
10	Correct	5 ms	1784 KB	Output is correct
11	Correct	5 ms	1400 KB	Output is correct
12	Correct	9 ms	2040 KB	Output is correct
13	Correct	5 ms	1912 KB	Output is correct
14	Correct	5 ms	1912 KB	Output is correct
15	Correct	18 ms	3576 KB	Output is correct
16	Correct	20 ms	3704 KB	Output is correct
17	Correct	14 ms	3320 KB	Output is correct
18	Correct	12 ms	2936 KB	Output is correct

Subtask #2

61.25 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	22776 KB	Output is correct
2	Correct	67 ms	10612 KB	Output is correct
3	Correct	1214 ms	881660 KB	Output is correct
4	Correct	78 ms	14840 KB	Output is correct
5	Runtime error	970 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
6	Correct	1137 ms	57360 KB	Output is correct
7	Correct	29 ms	22520 KB	Output is correct
8	Correct	28 ms	22748 KB	Output is correct
9	Correct	4 ms	1016 KB	Output is correct
10	Correct	6 ms	4220 KB	Output is correct
11	Correct	24 ms	18936 KB	Output is correct
12	Correct	19 ms	16888 KB	Output is correct
13	Correct	65 ms	10716 KB	Output is correct
14	Correct	39 ms	7416 KB	Output is correct
15	Correct	264 ms	210424 KB	Output is correct
16	Correct	33 ms	5112 KB	Output is correct
17	Correct	179 ms	24052 KB	Output is correct
18	Correct	1010 ms	805672 KB	Output is correct
19	Correct	81 ms	14840 KB	Output is correct
20	Correct	268 ms	184124 KB	Output is correct
21	Correct	699 ms	497916 KB	Output is correct
22	Runtime error	955 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
23	Correct	350 ms	38720 KB	Output is correct
24	Runtime error	964 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
25	Runtime error	1115 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
26	Correct	569 ms	26332 KB	Output is correct
27	Correct	784 ms	35192 KB	Output is correct
28	Correct	1099 ms	57292 KB	Output is correct
29	Correct	1044 ms	56532 KB	Output is correct
30	Correct	908 ms	51128 KB	Output is correct
31	Correct	890 ms	67188 KB	Output is correct
32	Correct	675 ms	34228 KB	Output is correct