oj.uz

Submission #474816

# Submission time Handle Problem Language Result Execution time Memory
474816 2021-09-20T01:30:03 Z dqk Tracks in the Snow (BOI13_tracks) C++17
80.3125 / 100
 2000 ms 1048580 KB 
#include <bits/stdc++.h>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<char>> g(n, std::vector<char>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> g[i][j];
        }
    }
    std::vector<std::vector<int>> comp(n, std::vector<int>(m, 0));
    std::vector<std::set<int>> adj(n * m + 5);
    int num = 0;
    std::function<void(int, int, char)> dfs=[&](int x, int y, char c) {
        if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] == '.')
            return;
        if (comp[x][y] && comp[x][y] != num) {
            adj[comp[x][y]].insert(num);
            adj[num].insert(comp[x][y]);
        }
        if (comp[x][y] || g[x][y] != c)
            return;

        comp[x][y] = num;
        dfs(x + 1, y, c);
        dfs(x - 1, y, c);
        dfs(x, y + 1, c);
        dfs(x, y - 1, c);
    };
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < m; ++y) {
            if (comp[x][y] || g[x][y] == '.')
                continue;
            num++;
            dfs(x, y, g[x][y]);
        }
    }

    std::vector<int> d(num + 1, 0);
    std::queue<int> q;
    q.push(1);
    d[1] = 1;
    int ans = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (d[v] == 0) {
                q.push(v);
                d[v] = d[u] + 1;
                ans = std::max(ans, d[v]);
            }
        }
    }
    std::cout << ans << "\n";
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 18424 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 22 ms 10488 KB Output is correct
5 Correct 9 ms 5708 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 8 ms 4684 KB Output is correct
11 Correct 6 ms 3148 KB Output is correct
12 Correct 19 ms 6892 KB Output is correct
13 Correct 9 ms 5644 KB Output is correct
14 Correct 11 ms 5708 KB Output is correct
15 Correct 44 ms 18372 KB Output is correct
16 Correct 55 ms 18500 KB Output is correct
17 Correct 37 ms 17348 KB Output is correct
18 Correct 21 ms 10572 KB Output is correct

Subtask #2
50.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4300 KB Output is correct
2 Correct 192 ms 104888 KB Output is correct
3 Correct 1282 ms 987156 KB Output is correct
4 Correct 318 ms 223228 KB Output is correct
5 Correct 1432 ms 908044 KB Output is correct
6 Execution timed out 2118 ms 963116 KB Time limit exceeded
7 Correct 5 ms 4044 KB Output is correct
8 Correct 6 ms 4300 KB Output is correct
9 Correct 8 ms 4940 KB Output is correct
10 Correct 3 ms 2892 KB Output is correct
11 Correct 5 ms 3916 KB Output is correct
12 Correct 4 ms 2624 KB Output is correct
13 Correct 198 ms 104960 KB Output is correct
14 Correct 113 ms 60996 KB Output is correct
15 Correct 110 ms 66676 KB Output is correct
16 Correct 92 ms 44984 KB Output is correct
17 Correct 499 ms 270560 KB Output is correct
18 Correct 422 ms 262716 KB Output is correct
19 Correct 324 ms 223172 KB Output is correct
20 Correct 287 ms 215192 KB Output is correct
21 Correct 767 ms 577200 KB Output is correct
22 Correct 1438 ms 908052 KB Output is correct
23 Correct 957 ms 517628 KB Output is correct
24 Correct 842 ms 619664 KB Output is correct
25 Runtime error 1245 ms 1048580 KB Execution killed with signal 9
26 Runtime error 727 ms 1048580 KB Execution killed with signal 9
27 Runtime error 750 ms 1048580 KB Execution killed with signal 9
28 Execution timed out 2140 ms 964284 KB Time limit exceeded
29 Execution timed out 2137 ms 935268 KB Time limit exceeded
30 Execution timed out 2087 ms 1034640 KB Time limit exceeded
31 Execution timed out 2130 ms 755396 KB Time limit exceeded
32 Runtime error 794 ms 1048580 KB Execution killed with signal 9