oj.uz

Submission #757667

# Submission time Handle Problem Language Result Execution time Memory
757667 2023-06-13T14:28:07 Z drdilyor Tracks in the Snow (BOI13_tracks) C++17
80.3125 / 100
 2000 ms 1048576 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")

#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 117 ms 18664 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 448 KB Output is correct
4 Correct 72 ms 12640 KB Output is correct
5 Correct 10 ms 3572 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 4 ms 712 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 13 ms 3284 KB Output is correct
11 Correct 23 ms 3412 KB Output is correct
12 Correct 47 ms 6868 KB Output is correct
13 Correct 11 ms 3512 KB Output is correct
14 Correct 10 ms 3540 KB Output is correct
15 Correct 82 ms 16064 KB Output is correct
16 Correct 126 ms 18568 KB Output is correct
17 Correct 49 ms 11724 KB Output is correct
18 Correct 69 ms 12664 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 324 ms 73852 KB Output is correct
3 Correct 1382 ms 610740 KB Output is correct
4 Correct 394 ms 128068 KB Output is correct
5 Correct 945 ms 398600 KB Output is correct
6 Execution timed out 2085 ms 1041380 KB Time limit exceeded
7 Correct 5 ms 2004 KB Output is correct
8 Correct 5 ms 2260 KB Output is correct
9 Correct 12 ms 3412 KB Output is correct
10 Correct 4 ms 1484 KB Output is correct
11 Correct 4 ms 2004 KB Output is correct
12 Correct 3 ms 1252 KB Output is correct
13 Correct 297 ms 73376 KB Output is correct
14 Correct 156 ms 42828 KB Output is correct
15 Correct 102 ms 37916 KB Output is correct
16 Correct 144 ms 34660 KB Output is correct
17 Correct 787 ms 187388 KB Output is correct
18 Correct 427 ms 149060 KB Output is correct
19 Correct 374 ms 127816 KB Output is correct
20 Correct 316 ms 134472 KB Output is correct
21 Correct 826 ms 357596 KB Output is correct
22 Correct 923 ms 398024 KB Output is correct
23 Correct 1547 ms 362776 KB Output is correct
24 Correct 757 ms 353816 KB Output is correct
25 Execution timed out 2075 ms 599852 KB Time limit exceeded
26 Execution timed out 2108 ms 925608 KB Time limit exceeded
27 Execution timed out 2056 ms 1048576 KB Time limit exceeded
28 Runtime error 1948 ms 1048576 KB Execution killed with signal 9
29 Execution timed out 2040 ms 1048576 KB Time limit exceeded
30 Execution timed out 2012 ms 1048576 KB Time limit exceeded
31 Execution timed out 2078 ms 772968 KB Time limit exceeded
32 Execution timed out 2055 ms 1013480 KB Time limit exceeded