oj.uz

Submission #757707

# Submission time Handle Problem Language Result Execution time Memory
757707 2023-06-13T15:23:23 Z drdilyor Tracks in the Snow (BOI13_tracks) C++17
3.33333 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<string> mat(n);
    for (string& s : mat) {
        cin >> s;
    }
    auto id = [m](int i, int j) { return i* m + j;};
    vector<vector<pair<int,int>>> adj(n * m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (auto [di, dj] : {pair{0, -1}, {0, 1}, {-1, 0}, {1, 0}}) {
                int ni = i + di;
                int nj = j + dj;
                if (clamp(ni, 0,n-1) == ni && clamp(nj, 0, m-1) == nj) {
                    if (mat[ni][nj] == '.' || mat[i][j] == '.') continue;
                    int c = mat[i][j] != mat[ni][nj];
                    adj[id(i, j)].push_back({id(ni, nj), c});
                }
            }
        }
    }

    static constexpr int inf = 1e9;
    vector<int> dist(n*m, inf);
    vector<bool> vis(n*m, 0), vis2(n*m, 0);
    int res = 0;
    vector<int> stk;
    stk.reserve(200*1000*1000);
    auto dfs = [&](int i, int d) -> void {
        stk.clear();
        stk.push_back(i);
        while (stk.size()) {
            int i = stk.back();
            stk.pop_back();
            vis[i] = 1;
            dist[i] = d;
            for (auto [e, ec]: adj[i]) {
                if (vis[e]) continue;
                if (!ec)
                    stk.push_back(e);
            }
            res = max(res, dist[i]);
        }
    };
    auto dfs_min = [&](int i) -> int {
        stk.clear();
        stk.push_back(i);
        int res = inf;
        while (stk.size()) {
            int i = stk.back();
            stk.pop_back();
            vis2[i] = 1;
            for (auto [e, ec]: adj[i]) {
                if (ec) res = min(res, dist[e]);
                if (vis2[e]) continue;
                if (!ec)
                    stk.push_back(e);
            }
        }
        return res;
    };
    dfs(0, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vis[id(i, j)]) continue;
            if (mat[i][j] == '.') continue;
            int d = dfs_min(id(i, j))+1;
            dfs(id(i, j), d);
        }
    }
    cout << res << '\n';
    
    

    return 0;
}

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 18244 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 33 ms 11988 KB Output isn't correct
5 Incorrect 7 ms 3412 KB Output isn't correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Correct 1 ms 596 KB Output is correct
9 Incorrect 1 ms 596 KB Output isn't correct
10 Incorrect 9 ms 3244 KB Output isn't correct
11 Correct 8 ms 3284 KB Output is correct
12 Incorrect 18 ms 6612 KB Output isn't correct
13 Incorrect 6 ms 3412 KB Output isn't correct
14 Incorrect 7 ms 3412 KB Output isn't correct
15 Incorrect 38 ms 15816 KB Output isn't correct
16 Incorrect 51 ms 18200 KB Output isn't correct
17 Incorrect 30 ms 11612 KB Output isn't correct
18 Incorrect 35 ms 12128 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2260 KB Output isn't correct
2 Incorrect 138 ms 73548 KB Output isn't correct
3 Incorrect 857 ms 613400 KB Output isn't correct
4 Incorrect 223 ms 128440 KB Output isn't correct
5 Incorrect 611 ms 399684 KB Output isn't correct
6 Runtime error 1432 ms 1048576 KB Execution killed with signal 9
7 Incorrect 4 ms 2004 KB Output isn't correct
8 Incorrect 5 ms 2260 KB Output isn't correct
9 Incorrect 6 ms 3156 KB Output isn't correct
10 Incorrect 2 ms 1492 KB Output isn't correct
11 Incorrect 3 ms 2004 KB Output isn't correct
12 Incorrect 2 ms 1236 KB Output isn't correct
13 Incorrect 143 ms 73464 KB Output isn't correct
14 Incorrect 80 ms 42768 KB Output isn't correct
15 Incorrect 74 ms 38060 KB Output isn't correct
16 Incorrect 73 ms 34440 KB Output isn't correct
17 Incorrect 329 ms 187992 KB Output isn't correct
18 Incorrect 270 ms 149764 KB Output isn't correct
19 Incorrect 231 ms 128456 KB Output isn't correct
20 Incorrect 195 ms 135192 KB Output isn't correct
21 Incorrect 513 ms 359360 KB Output isn't correct
22 Incorrect 626 ms 399708 KB Output isn't correct
23 Incorrect 656 ms 364240 KB Output isn't correct
24 Incorrect 491 ms 355384 KB Output isn't correct
25 Incorrect 1139 ms 603092 KB Output isn't correct
26 Execution timed out 2103 ms 959220 KB Time limit exceeded
27 Runtime error 1469 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1484 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1586 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1486 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2075 ms 773964 KB Time limit exceeded
32 Runtime error 1438 ms 1048576 KB Execution killed with signal 9