oj.uz

Submission #757671

# Submission time Handle Problem Language Result Execution time Memory
757671 2023-06-13T14:35:02 Z drdilyor Tracks in the Snow (BOI13_tracks) C++17
29.0625 / 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), vis(n*m, 0);
    queue<int> cur, next;
    dist[0] = 0;
    cur.push(0);
    int res = 0;
    while (cur.size()) {
        int v = cur.front();
        vis[v] = 1;
        res = max(res, dist[v]);
        for (auto [e, ec]: adj[v]) {
            if (vis[e]) continue;
            dist[e] = min(dist[e], dist[v] + ec);
            if (ec) next.push(e);
            else cur.push(e);
        }
        cur.pop();
        if (cur.empty()) {
            cur.swap(next);
            next = {};
        }
    }
    cout << res+1 << '\n';
    

    return 0;
}

Subtask #1
5.0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2090 ms 434152 KB Time limit exceeded
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 2089 ms 111088 KB Time limit exceeded
4 Execution timed out 2090 ms 407704 KB Time limit exceeded
5 Execution timed out 2095 ms 429704 KB Time limit exceeded
6 Correct 0 ms 212 KB Output is correct
7 Execution timed out 2084 ms 111088 KB Time limit exceeded
8 Execution timed out 2082 ms 438356 KB Time limit exceeded
9 Correct 38 ms 852 KB Output is correct
10 Execution timed out 2084 ms 343860 KB Time limit exceeded
11 Execution timed out 2086 ms 347368 KB Time limit exceeded
12 Execution timed out 2087 ms 480616 KB Time limit exceeded
13 Execution timed out 2081 ms 419584 KB Time limit exceeded
14 Execution timed out 2080 ms 430088 KB Time limit exceeded
15 Execution timed out 2076 ms 457492 KB Time limit exceeded
16 Execution timed out 2101 ms 464952 KB Time limit exceeded
17 Execution timed out 2092 ms 394296 KB Time limit exceeded
18 Execution timed out 2089 ms 402880 KB Time limit exceeded

Subtask #2
24.0625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2388 KB Output is correct
2 Execution timed out 2077 ms 345352 KB Time limit exceeded
3 Execution timed out 2110 ms 777804 KB Time limit exceeded
4 Execution timed out 2082 ms 242044 KB Time limit exceeded
5 Correct 957 ms 432840 KB Output is correct
6 Runtime error 1590 ms 1048576 KB Execution killed with signal 9
7 Correct 4 ms 2132 KB Output is correct
8 Correct 4 ms 2388 KB Output is correct
9 Execution timed out 2078 ms 265368 KB Time limit exceeded
10 Correct 3 ms 1620 KB Output is correct
11 Correct 3 ms 2132 KB Output is correct
12 Correct 3 ms 1364 KB Output is correct
13 Execution timed out 2082 ms 354420 KB Time limit exceeded
14 Execution timed out 2095 ms 454208 KB Time limit exceeded
15 Correct 101 ms 41612 KB Output is correct
16 Execution timed out 2090 ms 306708 KB Time limit exceeded
17 Execution timed out 2088 ms 369424 KB Time limit exceeded
18 Correct 390 ms 164528 KB Output is correct
19 Execution timed out 2093 ms 242116 KB Time limit exceeded
20 Execution timed out 2090 ms 251972 KB Time limit exceeded
21 Execution timed out 2085 ms 495304 KB Time limit exceeded
22 Correct 915 ms 432776 KB Output is correct
23 Execution timed out 2090 ms 531068 KB Time limit exceeded
24 Correct 659 ms 388848 KB Output is correct
25 Execution timed out 2094 ms 661884 KB Time limit exceeded
26 Execution timed out 2062 ms 1048576 KB Time limit exceeded
27 Runtime error 1835 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1656 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1564 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1597 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2081 ms 1019804 KB Time limit exceeded
32 Runtime error 1531 ms 1048576 KB Execution killed with signal 9