oj.uz

Submission #332622

# Submission time Handle Problem Language Result Execution time Memory
332622 2020-12-03T01:38:45 Z izhang05 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1000 ms 146592 KB 
#include <bits/stdc++.h>

using namespace std;

mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count());
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>
using indexed_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int maxn = 4001;
int dist[maxn][maxn], n, m;
char grid[maxn][maxn];

bool pos(pair<int, int> x) {
    return x.first >= 0 && x.second >= 0 && x.first < n && x.second < m;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
            dist[i][j] = 1e9;
        }
    }
    dist[0][0] = 0;
    deque<pair<int, pair<int, int>>> q;
    q.push_front(make_pair(0, make_pair(0, 0)));
    while (!q.empty()) {
        int d = q.front().first;
        pair<int, int> l = q.front().second;
        q.pop_front();
        for (int i = 0; i < 4; ++i) {
            pair<int, int> next = make_pair(l.first + dx[i], +l.second + dy[i]);
            if (pos(next) && grid[next.first][next.second] != '.') {
                if (grid[l.first][l.second] == grid[next.first][next.second] && dist[next.first][next.second] > d) {
                    q.push_front(make_pair(dist[next.first][next.second] = d, next));
                } else {
                    if (dist[next.first][next.second] > d + 1) {
                        q.emplace_back(dist[next.first][next.second] = d + 1, next);
                    }
                }
            }
        }
    }
    int sol = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (dist[i][j] != 1e9) {
                sol = max(sol, dist[i][j]);
            }
        }
    }
    cout << sol + 1 << "\n";
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5484 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 12 ms 5336 KB Output is correct
5 Correct 5 ms 3052 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 1 ms 1132 KB Output is correct
10 Correct 4 ms 2668 KB Output is correct
11 Correct 4 ms 2284 KB Output is correct
12 Correct 8 ms 3180 KB Output is correct
13 Correct 5 ms 3052 KB Output is correct
14 Correct 5 ms 3052 KB Output is correct
15 Correct 17 ms 5612 KB Output is correct
16 Correct 20 ms 5484 KB Output is correct
17 Correct 15 ms 5356 KB Output is correct
18 Correct 12 ms 5356 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30956 KB Output is correct
2 Correct 74 ms 17940 KB Output is correct
3 Correct 465 ms 82152 KB Output is correct
4 Correct 135 ms 33644 KB Output is correct
5 Correct 296 ms 62828 KB Output is correct
6 Correct 987 ms 103120 KB Output is correct
7 Correct 21 ms 32364 KB Output is correct
8 Correct 20 ms 30956 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 19 ms 31724 KB Output is correct
12 Correct 3 ms 1644 KB Output is correct
13 Correct 74 ms 17900 KB Output is correct
14 Correct 54 ms 12012 KB Output is correct
15 Correct 43 ms 13164 KB Output is correct
16 Correct 33 ms 6636 KB Output is correct
17 Correct 191 ms 35820 KB Output is correct
18 Correct 154 ms 35564 KB Output is correct
19 Correct 136 ms 33644 KB Output is correct
20 Correct 111 ms 31084 KB Output is correct
21 Correct 282 ms 64808 KB Output is correct
22 Correct 279 ms 62700 KB Output is correct
23 Correct 356 ms 53100 KB Output is correct
24 Correct 267 ms 64236 KB Output is correct
25 Correct 707 ms 82284 KB Output is correct
26 Correct 632 ms 146592 KB Output is correct
27 Correct 838 ms 133352 KB Output is correct
28 Correct 1000 ms 103148 KB Output is correct
29 Correct 984 ms 99384 KB Output is correct
30 Correct 909 ms 109356 KB Output is correct
31 Correct 851 ms 67780 KB Output is correct
32 Correct 754 ms 118380 KB Output is correct