oj.uz

Submission #757666

# Submission time Handle Problem Language Result Execution time Memory
757666 2023-06-13T14:27:23 Z drdilyor Tracks in the Snow (BOI13_tracks) C++17
80.3125 / 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});
                }
            }
        }
    }

    vector<int> dist(n*m, -1);
    priority_queue<pair<int,int>> p;
    p.push({0, 0});
    while (p.size()) {
        auto [w, v] = p.top();
        p.pop();
        if (dist[v] != -1) continue;
        dist[v] = -w;
        for (auto [e, ew]: adj[v]) {
            if (dist[e] == -1) {
                p.push({w - ew, e});
            }
        }
    }
    cout << *max_element(dist.begin(), dist.end()) +1 << '\n';
    

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 18636 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 61 ms 12628 KB Output is correct
5 Correct 10 ms 3540 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 11 ms 3344 KB Output is correct
11 Correct 23 ms 3512 KB Output is correct
12 Correct 44 ms 6868 KB Output is correct
13 Correct 9 ms 3540 KB Output is correct
14 Correct 9 ms 3540 KB Output is correct
15 Correct 73 ms 16096 KB Output is correct
16 Correct 102 ms 18644 KB Output is correct
17 Correct 45 ms 11776 KB Output is correct
18 Correct 62 ms 12708 KB Output is correct

Subtask #2
50.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2260 KB Output is correct
2 Correct 270 ms 74736 KB Output is correct
3 Correct 1142 ms 617656 KB Output is correct
4 Correct 330 ms 131220 KB Output is correct
5 Correct 748 ms 404940 KB Output is correct
6 Runtime error 1835 ms 1048576 KB Execution killed with signal 9
7 Correct 4 ms 2004 KB Output is correct
8 Correct 3 ms 2260 KB Output is correct
9 Correct 9 ms 3408 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 3 ms 2004 KB Output is correct
12 Correct 3 ms 1228 KB Output is correct
13 Correct 268 ms 74744 KB Output is correct
14 Correct 147 ms 43468 KB Output is correct
15 Correct 88 ms 38600 KB Output is correct
16 Correct 131 ms 35024 KB Output is correct
17 Correct 710 ms 191064 KB Output is correct
18 Correct 371 ms 152652 KB Output is correct
19 Correct 321 ms 131148 KB Output is correct
20 Correct 274 ms 137724 KB Output is correct
21 Correct 671 ms 364992 KB Output is correct
22 Correct 698 ms 405252 KB Output is correct
23 Correct 1341 ms 368712 KB Output is correct
24 Correct 620 ms 360908 KB Output is correct
25 Execution timed out 2103 ms 607548 KB Time limit exceeded
26 Execution timed out 2053 ms 934140 KB Time limit exceeded
27 Runtime error 1799 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1800 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1770 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1862 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2104 ms 781064 KB Time limit exceeded
32 Runtime error 1768 ms 1048576 KB Execution killed with signal 9