Submission #134083

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
134083	2019-07-22T04:10:50 Z	fredbr	Tracks in the Snow (BOI13_tracks)	C++17	97.8125 / 100	1454 ms	1048580 KB

tracks

#include <bits/stdc++.h>

using namespace std;

int const maxn = 4010;

int cnt = 0;
int n, m;
char vis[maxn][maxn];
char v[maxn][maxn];

using ii = pair<int, int>;

vector<ii> nxt;

static int const dx[] = {0, 1, 0, -1};
static int const dy[] = {1, 0, -1, 0};

void dfs(int x, int y) {

    if (vis[x][y]) return;
    if (v[x][y] == '.') return;

    vis[x][y] = 1;
    cnt--;

    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];

        if (xx >= 0 and xx < n and yy >= 0 and yy < m) {
            if (vis[xx][yy]) continue;

            if (v[xx][yy] == v[x][y]) dfs(xx, yy);
            else if (v[xx][yy] != '.' and !vis[xx][yy]) {
                nxt.emplace_back(xx, yy);
            }
        }
    }
    v[x][y] = '.';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> v[i][j];
            if (v[i][j] != '.') cnt++;
        }
    }

    int ans = 0;
    nxt.emplace_back(0, 0);
    nxt.emplace_back(n-1, m-1);

    vector<ii> nxt2;

    while (cnt > 0) {
        swap(nxt, nxt2);

        for (auto i : nxt2) {
            dfs(i.first, i.second);
        }

        nxt2.clear();
        ans++;
    }

    cout << ans << "\n";
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	4600 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	760 KB	Output is correct
4	Correct	16 ms	6520 KB	Output is correct
5	Correct	7 ms	2680 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 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	2424 KB	Output is correct
11	Correct	6 ms	2908 KB	Output is correct
12	Correct	12 ms	3032 KB	Output is correct
13	Correct	7 ms	2652 KB	Output is correct
14	Correct	7 ms	2652 KB	Output is correct
15	Correct	20 ms	4600 KB	Output is correct
16	Correct	23 ms	4728 KB	Output is correct
17	Correct	17 ms	4344 KB	Output is correct
18	Correct	15 ms	6520 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	30768 KB	Output is correct
2	Correct	69 ms	10604 KB	Output is correct
3	Correct	424 ms	32692 KB	Output is correct
4	Correct	117 ms	15700 KB	Output is correct
5	Correct	257 ms	24568 KB	Output is correct
6	Correct	1064 ms	171976 KB	Output is correct
7	Correct	33 ms	32120 KB	Output is correct
8	Correct	32 ms	30712 KB	Output is correct
9	Correct	5 ms	1016 KB	Output is correct
10	Correct	3 ms	760 KB	Output is correct
11	Correct	33 ms	31580 KB	Output is correct
12	Correct	4 ms	1528 KB	Output is correct
13	Correct	74 ms	10496 KB	Output is correct
14	Correct	41 ms	7800 KB	Output is correct
15	Correct	40 ms	8440 KB	Output is correct
16	Correct	33 ms	3832 KB	Output is correct
17	Correct	168 ms	16760 KB	Output is correct
18	Correct	140 ms	16504 KB	Output is correct
19	Correct	117 ms	15620 KB	Output is correct
20	Correct	101 ms	14608 KB	Output is correct
21	Correct	248 ms	25336 KB	Output is correct
22	Correct	264 ms	24572 KB	Output is correct
23	Correct	315 ms	20728 KB	Output is correct
24	Correct	243 ms	25536 KB	Output is correct
25	Correct	560 ms	32632 KB	Output is correct
26	Runtime error	1096 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
27	Correct	1454 ms	859848 KB	Output is correct
28	Correct	1047 ms	171836 KB	Output is correct
29	Correct	986 ms	146148 KB	Output is correct
30	Correct	1104 ms	348612 KB	Output is correct
31	Correct	767 ms	28016 KB	Output is correct
32	Correct	1278 ms	624964 KB	Output is correct