oj.uz

Submission #1049532

# Submission time Handle Problem Language Result Execution time Memory
1049532 2024-08-08T20:58:12 Z inkvizytor Tracks in the Snow (BOI13_tracks) C++17
89.0625 / 100
 1606 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    vector<string> s (h);
    cin >> s[0] >> s[1];
    vector<vector<pair<int, bool>>> g (h*w);
    for (int i = 0; i < h; i++) {
        if (i < h-2) {
            cin >> s[i+2];
        }
        for (int j = 0; j < w; j++) {
            if (s[i][j] == '.') continue;
            if (i != 0 && s[i-1][j] != '.') {
                g[i*w+j].push_back({(i-1)*w+j, s[i][j]==s[i-1][j]});
            }
            if (j != 0 && s[i][j-1] != '.') {
                g[i*w+j].push_back({i*w+j-1, s[i][j]==s[i][j-1]});
            }
            if (i != h-1 && s[i+1][j] != '.') {
                g[i*w+j].push_back({(i+1)*w+j, s[i][j]==s[i+1][j]});
            }
            if (j != w-1 && s[i][j+1] != '.') {
                g[i*w+j].push_back({i*w+j+1, s[i][j]==s[i][j+1]});
            }
        }
        if (i > 0) {
            s[i-1] = "";
        }
    }
    s.resize(0);
    deque<pair<int, int>> q;
    vector<bool> odw (h*w, 0);
    q.push_back({0, 1});
    int maxd = 0;
    while (!q.empty()) {
        auto x = q.front();
        q.pop_front();
        if (odw[x.first]) {
            continue;
        }
        maxd = max(maxd, x.second);
        odw[x.first] = 1;
        for (auto i : g[x.first]) {
            if (odw[i.first]) continue;
            if (i.second) {
                q.push_front({i.first, x.second});
            }
            else {
                q.push_back({i.first, x.second+1});
            }
        }
    }
    cout << maxd << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 17500 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 15 ms 11708 KB Output is correct
5 Correct 3 ms 3160 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 4 ms 3164 KB Output is correct
11 Correct 4 ms 3420 KB Output is correct
12 Correct 12 ms 6472 KB Output is correct
13 Correct 3 ms 3164 KB Output is correct
14 Correct 3 ms 3160 KB Output is correct
15 Correct 24 ms 14872 KB Output is correct
16 Correct 32 ms 17636 KB Output is correct
17 Correct 13 ms 10608 KB Output is correct
18 Correct 19 ms 11868 KB Output is correct

Subtask #2
59.0625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2136 KB Output is correct
2 Correct 82 ms 67364 KB Output is correct
3 Correct 485 ms 548852 KB Output is correct
4 Correct 128 ms 113412 KB Output is correct
5 Correct 333 ms 363600 KB Output is correct
6 Runtime error 963 ms 1048576 KB Execution killed with signal 9
7 Correct 2 ms 1880 KB Output is correct
8 Correct 2 ms 2140 KB Output is correct
9 Correct 3 ms 2908 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 1 ms 1884 KB Output is correct
12 Correct 1 ms 1372 KB Output is correct
13 Correct 82 ms 67344 KB Output is correct
14 Correct 43 ms 39028 KB Output is correct
15 Correct 31 ms 33872 KB Output is correct
16 Correct 46 ms 31828 KB Output is correct
17 Correct 222 ms 171600 KB Output is correct
18 Correct 132 ms 133716 KB Output is correct
19 Correct 124 ms 113240 KB Output is correct
20 Correct 88 ms 121424 KB Output is correct
21 Correct 246 ms 321868 KB Output is correct
22 Correct 344 ms 363564 KB Output is correct
23 Correct 427 ms 332908 KB Output is correct
24 Correct 242 ms 318804 KB Output is correct
25 Correct 583 ms 538964 KB Output is correct
26 Correct 1111 ms 966664 KB Output is correct
27 Runtime error 948 ms 1048576 KB Execution killed with signal 9
28 Runtime error 985 ms 1048576 KB Execution killed with signal 9
29 Runtime error 990 ms 1048576 KB Execution killed with signal 9
30 Runtime error 962 ms 1048576 KB Execution killed with signal 9
31 Correct 1606 ms 732760 KB Output is correct
32 Correct 1398 ms 1048576 KB Output is correct