oj.uz

Submission #474814

# Submission time Handle Problem Language Result Execution time Memory
474814 2021-09-20T01:20:25 Z dqk Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 1971 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, -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 8 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 460 KB Execution killed with signal 11
4 Runtime error 10 ms 4300 KB Execution killed with signal 11
5 Runtime error 3 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 460 KB Execution killed with signal 11
8 Runtime error 1 ms 580 KB Execution killed with signal 11
9 Runtime error 1 ms 588 KB Execution killed with signal 11
10 Runtime error 3 ms 1220 KB Execution killed with signal 11
11 Runtime error 4 ms 1604 KB Execution killed with signal 11
12 Runtime error 4 ms 1612 KB Execution killed with signal 11
13 Runtime error 4 ms 1484 KB Execution killed with signal 11
14 Runtime error 4 ms 1484 KB Execution killed with signal 11
15 Runtime error 8 ms 3524 KB Execution killed with signal 11
16 Runtime error 10 ms 3532 KB Execution killed with signal 11
17 Runtime error 9 ms 3392 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 6 ms 2764 KB Execution killed with signal 11
2 Runtime error 40 ms 18632 KB Execution killed with signal 11
3 Runtime error 375 ms 178648 KB Execution killed with signal 11
4 Runtime error 98 ms 43460 KB Execution killed with signal 11
5 Runtime error 214 ms 102476 KB Execution killed with signal 11
6 Runtime error 701 ms 237944 KB Execution killed with signal 11
7 Runtime error 5 ms 2876 KB Execution killed with signal 11
8 Runtime error 5 ms 2764 KB Execution killed with signal 11
9 Runtime error 4 ms 1996 KB Execution killed with signal 11
10 Runtime error 3 ms 1484 KB Execution killed with signal 11
11 Runtime error 14 ms 4044 KB Execution killed with signal 6
12 Runtime error 1 ms 712 KB Execution killed with signal 11
13 Runtime error 40 ms 18640 KB Execution killed with signal 11
14 Runtime error 25 ms 11084 KB Execution killed with signal 11
15 Runtime error 26 ms 12148 KB Execution killed with signal 11
16 Runtime error 17 ms 8140 KB Execution killed with signal 11
17 Runtime error 104 ms 46960 KB Execution killed with signal 11
18 Runtime error 97 ms 46276 KB Execution killed with signal 11
19 Runtime error 93 ms 43460 KB Execution killed with signal 11
20 Runtime error 83 ms 39812 KB Execution killed with signal 11
21 Runtime error 223 ms 106172 KB Execution killed with signal 11
22 Runtime error 210 ms 102512 KB Execution killed with signal 11
23 Runtime error 213 ms 88560 KB Execution killed with signal 11
24 Runtime error 213 ms 103676 KB Execution killed with signal 11
25 Runtime error 379 ms 178400 KB Execution killed with signal 11
26 Runtime error 1066 ms 1048580 KB Execution killed with signal 9
27 Runtime error 1652 ms 778348 KB Execution killed with signal 11
28 Runtime error 688 ms 227592 KB Execution killed with signal 11
29 Runtime error 763 ms 246024 KB Execution killed with signal 11
30 Runtime error 713 ms 228088 KB Execution killed with signal 11
31 Runtime error 273 ms 109772 KB Execution killed with signal 11
32 Runtime error 1971 ms 832128 KB Execution killed with signal 11