oj.uz

Submission #474813

# Submission time Handle Problem Language Result Execution time Memory
474813 2021-09-20T01:16:29 Z dqk Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 1875 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::string> g(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> g[i];
    }
    std::vector<std::vector<int>> comp(n, std::vector<int>(m, -1));
    std::vector<std::vector<bool>> connect(n, std::vector<bool>(m, false));
    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] != -1 && comp[x][y] != num) {
            connect[num][comp[x][y]] = true;
            connect[comp[x][y]][num] =  true;
        }
        if (comp[x][y] != -1 || 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] != -1 || g[x][y] == '.')
                continue;
            dfs(x, y, g[x][y]);
            num++;
        }
    }
    std::vector<std::vector<int>> adj(num);
    for (int i = 0; i < num; ++i) {
        for (int j = i + 1; j < num; ++j) {
            if (connect[i][j]) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    std::vector<int> d(num, 0);
    std::queue<int> q;
    q.push(0);
    d[0] = 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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 3532 KB Execution killed with signal 11
2 Runtime error 1 ms 460 KB Execution killed with signal 11
3 Runtime error 1 ms 440 KB Execution killed with signal 11
4 Runtime error 9 ms 4348 KB Execution killed with signal 11
5 Runtime error 2 ms 1484 KB Execution killed with signal 11
6 Runtime error 1 ms 332 KB Execution killed with signal 11
7 Runtime error 1 ms 484 KB Execution killed with signal 11
8 Runtime error 1 ms 588 KB Execution killed with signal 11
9 Runtime error 1 ms 588 KB Execution killed with signal 11
10 Runtime error 2 ms 1228 KB Execution killed with signal 11
11 Runtime error 3 ms 1612 KB Execution killed with signal 11
12 Runtime error 2 ms 1612 KB Execution killed with signal 11
13 Runtime error 2 ms 1484 KB Execution killed with signal 11
14 Runtime error 2 ms 1484 KB Execution killed with signal 11
15 Runtime error 4 ms 3532 KB Execution killed with signal 11
16 Runtime error 4 ms 3524 KB Execution killed with signal 11
17 Runtime error 4 ms 3404 KB Execution killed with signal 11
18 Runtime error 10 ms 4300 KB Execution killed with signal 11

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 2636 KB Execution killed with signal 11
2 Runtime error 17 ms 18780 KB Execution killed with signal 11
3 Runtime error 145 ms 185428 KB Execution killed with signal 11
4 Runtime error 36 ms 43944 KB Execution killed with signal 11
5 Runtime error 84 ms 104368 KB Execution killed with signal 11
6 Runtime error 454 ms 244784 KB Execution killed with signal 11
7 Runtime error 4 ms 2764 KB Execution killed with signal 11
8 Runtime error 4 ms 2636 KB Execution killed with signal 11
9 Runtime error 3 ms 1996 KB Execution killed with signal 11
10 Runtime error 2 ms 1484 KB Execution killed with signal 11
11 Runtime error 14 ms 3752 KB Execution killed with signal 6
12 Runtime error 1 ms 716 KB Execution killed with signal 11
13 Runtime error 18 ms 18892 KB Execution killed with signal 11
14 Runtime error 11 ms 11216 KB Execution killed with signal 11
15 Runtime error 12 ms 12236 KB Execution killed with signal 11
16 Runtime error 8 ms 8260 KB Execution killed with signal 11
17 Runtime error 42 ms 47556 KB Execution killed with signal 11
18 Runtime error 42 ms 46820 KB Execution killed with signal 11
19 Runtime error 42 ms 44036 KB Execution killed with signal 11
20 Runtime error 36 ms 40416 KB Execution killed with signal 11
21 Runtime error 90 ms 108020 KB Execution killed with signal 11
22 Runtime error 85 ms 104360 KB Execution killed with signal 11
23 Runtime error 76 ms 90108 KB Execution killed with signal 11
24 Runtime error 85 ms 105436 KB Execution killed with signal 11
25 Runtime error 163 ms 185336 KB Execution killed with signal 11
26 Runtime error 949 ms 1048580 KB Execution killed with signal 9
27 Runtime error 1593 ms 795632 KB Execution killed with signal 11
28 Runtime error 470 ms 244800 KB Execution killed with signal 11
29 Runtime error 551 ms 263188 KB Execution killed with signal 11
30 Runtime error 513 ms 244892 KB Execution killed with signal 11
31 Runtime error 114 ms 119228 KB Execution killed with signal 11
32 Runtime error 1875 ms 849368 KB Execution killed with signal 11