oj.uz

Submission #474815

# Submission time Handle Problem Language Result Execution time Memory
474815 2021-09-20T01:22:38 Z dqk Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 1929 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(n + m);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < m; ++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 10 ms 3532 KB Execution killed with signal 11
2 Runtime error 2 ms 332 KB Execution killed with signal 11
3 Runtime error 1 ms 460 KB Execution killed with signal 11
4 Runtime error 10 ms 4248 KB Execution killed with signal 11
5 Runtime error 4 ms 1540 KB Execution killed with signal 11
6 Runtime error 1 ms 460 KB Execution killed with signal 11
7 Runtime error 1 ms 460 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 3 ms 1228 KB Execution killed with signal 11
11 Runtime error 4 ms 1612 KB Execution killed with signal 11
12 Runtime error 4 ms 1612 KB Execution killed with signal 11
13 Runtime error 3 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 3512 KB Execution killed with signal 11
16 Runtime error 9 ms 3508 KB Execution killed with signal 11
17 Runtime error 7 ms 3404 KB Execution killed with signal 11
18 Runtime error 11 ms 4300 KB Execution killed with signal 11

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 2892 KB Execution killed with signal 11
2 Runtime error 40 ms 17868 KB Execution killed with signal 11
3 Runtime error 370 ms 167112 KB Execution killed with signal 11
4 Runtime error 92 ms 40516 KB Execution killed with signal 11
5 Runtime error 219 ms 94328 KB Execution killed with signal 11
6 Runtime error 709 ms 226544 KB Execution killed with signal 11
7 Runtime error 5 ms 2892 KB Execution killed with signal 11
8 Runtime error 5 ms 2808 KB Execution killed with signal 11
9 Runtime error 3 ms 1996 KB Execution killed with signal 11
10 Runtime error 3 ms 1484 KB Execution killed with signal 11
11 Runtime error 5 ms 3148 KB Execution killed with signal 6
12 Runtime error 1 ms 716 KB Execution killed with signal 11
13 Runtime error 41 ms 17888 KB Execution killed with signal 11
14 Runtime error 24 ms 10944 KB Execution killed with signal 11
15 Runtime error 26 ms 11944 KB Execution killed with signal 11
16 Runtime error 17 ms 8140 KB Execution killed with signal 11
17 Runtime error 99 ms 43780 KB Execution killed with signal 11
18 Runtime error 98 ms 43076 KB Execution killed with signal 11
19 Runtime error 94 ms 40516 KB Execution killed with signal 11
20 Runtime error 82 ms 37264 KB Execution killed with signal 11
21 Runtime error 216 ms 97728 KB Execution killed with signal 11
22 Runtime error 215 ms 94348 KB Execution killed with signal 11
23 Runtime error 182 ms 81716 KB Execution killed with signal 11
24 Runtime error 212 ms 95428 KB Execution killed with signal 11
25 Runtime error 376 ms 167076 KB Execution killed with signal 11
26 Runtime error 1014 ms 1048580 KB Execution killed with signal 9
27 Runtime error 1596 ms 776432 KB Execution killed with signal 11
28 Runtime error 701 ms 225356 KB Execution killed with signal 11
29 Runtime error 732 ms 243752 KB Execution killed with signal 11
30 Runtime error 743 ms 225824 KB Execution killed with signal 11
31 Runtime error 247 ms 107332 KB Execution killed with signal 11
32 Runtime error 1929 ms 829920 KB Execution killed with signal 11