oj.uz

Submission #474823

# Submission time Handle Problem Language Result Execution time Memory
474823 2021-09-20T01:41:44 Z dqk Tracks in the Snow (BOI13_tracks) C++17
95.625 / 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::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, 0));
    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 || 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<std::vector<int>> adj(num + 1);
    auto addcomp=[&](int i, int j) {
        auto add=[&](int x, int y) {
            if (x < 0 || x >= n || y < 0 || y >= m)
                return;
            if (comp[x][y] && comp[x][y] != comp[i][j]) {
                adj[comp[x][y]].push_back(comp[i][j]);
                adj[comp[i][j]].push_back(comp[x][y]);
            }
        };
        add(i - 1, j);
        add(i + 1, j);
        add(i, j + 1);
        add(i, j - 1);
    };
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (comp[i][j])
                addcomp(i, j); 
        }
    }
    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 57 ms 7940 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 17 ms 3084 KB Output is correct
5 Correct 6 ms 1356 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 6 ms 1340 KB Output is correct
11 Correct 5 ms 1100 KB Output is correct
12 Correct 16 ms 3020 KB Output is correct
13 Correct 5 ms 1356 KB Output is correct
14 Correct 5 ms 1356 KB Output is correct
15 Correct 36 ms 6580 KB Output is correct
16 Correct 45 ms 7912 KB Output is correct
17 Correct 26 ms 4556 KB Output is correct
18 Correct 14 ms 3144 KB Output is correct

Subtask #2
65.625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1356 KB Output is correct
2 Correct 152 ms 26956 KB Output is correct
3 Correct 772 ms 192152 KB Output is correct
4 Correct 171 ms 36088 KB Output is correct
5 Correct 1084 ms 309680 KB Output is correct
6 Correct 1564 ms 239104 KB Output is correct
7 Correct 3 ms 1356 KB Output is correct
8 Correct 4 ms 1356 KB Output is correct
9 Correct 6 ms 1740 KB Output is correct
10 Correct 2 ms 972 KB Output is correct
11 Correct 3 ms 1228 KB Output is correct
12 Correct 3 ms 1100 KB Output is correct
13 Correct 141 ms 26824 KB Output is correct
14 Correct 81 ms 15788 KB Output is correct
15 Correct 72 ms 13844 KB Output is correct
16 Correct 74 ms 13500 KB Output is correct
17 Correct 365 ms 68136 KB Output is correct
18 Correct 266 ms 52956 KB Output is correct
19 Correct 172 ms 36072 KB Output is correct
20 Correct 183 ms 43472 KB Output is correct
21 Correct 475 ms 113568 KB Output is correct
22 Correct 1070 ms 309832 KB Output is correct
23 Correct 782 ms 132420 KB Output is correct
24 Correct 511 ms 134240 KB Output is correct
25 Correct 1274 ms 215248 KB Output is correct
26 Runtime error 889 ms 1048580 KB Execution killed with signal 9
27 Correct 1292 ms 389168 KB Output is correct
28 Correct 1559 ms 239120 KB Output is correct
29 Correct 1466 ms 211740 KB Output is correct
30 Correct 1464 ms 254956 KB Output is correct
31 Execution timed out 2109 ms 324612 KB Time limit exceeded
32 Correct 1427 ms 422064 KB Output is correct