oj.uz

Submission #814300

# Submission time Handle Problem Language Result Execution time Memory
814300 2023-08-08T06:44:08 Z asdasdqwer Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 957 ms 257620 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define pii pair<int, int>

vector<pii> dir = {{0, 1}, {-1, 0}, {1, 0}, {0, -1}};
int n, m;

pii operator+(const pii &x, const pii &y) {
    return {x.first + y.first, x.second + y.second};
}

bool check(const pii &x) {
    return x.first >= 0 && x.first < n && x.second >= 0 && x.second < m;
}

signed main() {
    cin>>n>>m;
    vector<string> a(n);
    for (auto &x:a)cin>>x;
    vector<vector<int>> d(n, vector<int>(m, 1e9));
    deque<pii> dq;
    dq.push_front({0, 0});
    d[0][0]=1;
    int mx = 0;
    while (!dq.empty()) {
        pii t = dq.front();dq.pop_front();
        mx = max(mx, d[t.first][t.second]);
        // test all dir
        for (pii x:dir) {
            pii temp = t + x;
            if (check(temp) && a[temp.first][temp.second] != '.') {
                int w = (a[t.first][t.second] != a[temp.first][temp.second]);
                if (d[t.first][t.second] + w < d[temp.first][temp.second]) {
                    if (w == 0) {
                        dq.push_front(temp);
                    }

                    else {
                        dq.push_back(temp);
                    }
                    d[temp.first][temp.second]=d[t.first][t.second]+w;
                }
            }
        }
    }

    cout << mx << "\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3028 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 7 ms 2260 KB Output is correct
5 Correct 3 ms 1196 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 5 ms 1292 KB Output is correct
13 Correct 3 ms 1208 KB Output is correct
14 Correct 4 ms 1208 KB Output is correct
15 Correct 15 ms 3068 KB Output is correct
16 Correct 12 ms 3048 KB Output is correct
17 Correct 10 ms 2916 KB Output is correct
18 Correct 7 ms 2360 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 952 KB Output is correct
2 Correct 68 ms 16484 KB Output is correct
3 Correct 438 ms 158256 KB Output is correct
4 Correct 113 ms 39176 KB Output is correct
5 Correct 228 ms 84588 KB Output is correct
6 Correct 875 ms 200964 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 3 ms 980 KB Output is correct
9 Correct 2 ms 948 KB Output is correct
10 Correct 1 ms 564 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 50 ms 16532 KB Output is correct
14 Correct 30 ms 10032 KB Output is correct
15 Correct 29 ms 10964 KB Output is correct
16 Correct 22 ms 6708 KB Output is correct
17 Correct 178 ms 42040 KB Output is correct
18 Correct 108 ms 41496 KB Output is correct
19 Correct 99 ms 39104 KB Output is correct
20 Correct 86 ms 36268 KB Output is correct
21 Correct 222 ms 87436 KB Output is correct
22 Correct 214 ms 84504 KB Output is correct
23 Correct 254 ms 72896 KB Output is correct
24 Correct 216 ms 85760 KB Output is correct
25 Correct 576 ms 158268 KB Output is correct
26 Correct 724 ms 221912 KB Output is correct
27 Correct 820 ms 257620 KB Output is correct
28 Correct 957 ms 200980 KB Output is correct
29 Correct 783 ms 194192 KB Output is correct
30 Correct 788 ms 208676 KB Output is correct
31 Correct 499 ms 95924 KB Output is correct
32 Correct 795 ms 217932 KB Output is correct