oj.uz

Submission #594725

# Submission time Handle Problem Language Result Execution time Memory
594725 2022-07-12T21:48:23 Z bogdanvladmihai Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1533 ms 122884 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = INT_MAX / 2;
const int MAXN = 4000;
const int ox[] = {0, 1, 0, -1};
const int oy[] = {1, 0, -1, 0};

int n, m;
char mat[MAXN + 1][MAXN + 1];
int cost[MAXN + 1][MAXN + 1];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mat[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cost[i][j] = INF;
        }
    }

    deque<pair<int, int>> dq;
    cost[0][0] = 1;
    dq.push_front(make_pair(0, 0));
    while (!dq.empty()) {
        int x, y;
        tie(x, y) = dq.front();
        dq.pop_front();

        for (int i = 0; i < 4; i++) {
            int nx = x + ox[i];
            int ny = y + oy[i];
            if (nx < 0 || ny < 0 || nx == n || ny == m) {
                continue;
            }
            if (mat[nx][ny] == '.') {
                continue;
            }

            int t = 0;
            if (mat[nx][ny] != mat[x][y]) {
                t = 1;
            }
            if (cost[nx][ny] > cost[x][y] + t) {
                cost[nx][ny] = t + cost[x][y];
                if (t) {
                    dq.push_back(make_pair(nx, ny));
                } else {
                    dq.push_front(make_pair(nx, ny));
                }
            }
        }
    }

    int ans = -INF;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mat[i][j] == '.') {
                continue;
//                cerr << "oo ";
            }

//            cerr << cost[i][j] << " ";
            ans = max(ans, cost[i][j]);
        }
//        cerr << "\n";
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5408 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 16 ms 5188 KB Output is correct
5 Correct 8 ms 3004 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 7 ms 2516 KB Output is correct
11 Correct 6 ms 2132 KB Output is correct
12 Correct 11 ms 3008 KB Output is correct
13 Correct 7 ms 2900 KB Output is correct
14 Correct 8 ms 2992 KB Output is correct
15 Correct 27 ms 5440 KB Output is correct
16 Correct 26 ms 5428 KB Output is correct
17 Correct 21 ms 5176 KB Output is correct
18 Correct 15 ms 5120 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30804 KB Output is correct
2 Correct 120 ms 17868 KB Output is correct
3 Correct 1018 ms 82616 KB Output is correct
4 Correct 257 ms 33624 KB Output is correct
5 Correct 566 ms 63012 KB Output is correct
6 Correct 1502 ms 96924 KB Output is correct
7 Correct 14 ms 32268 KB Output is correct
8 Correct 14 ms 30804 KB Output is correct
9 Correct 5 ms 596 KB Output is correct
10 Correct 2 ms 452 KB Output is correct
11 Correct 14 ms 31700 KB Output is correct
12 Correct 2 ms 1492 KB Output is correct
13 Correct 141 ms 17840 KB Output is correct
14 Correct 79 ms 11936 KB Output is correct
15 Correct 68 ms 13056 KB Output is correct
16 Correct 52 ms 6580 KB Output is correct
17 Correct 303 ms 36044 KB Output is correct
18 Correct 311 ms 35660 KB Output is correct
19 Correct 245 ms 33576 KB Output is correct
20 Correct 226 ms 31020 KB Output is correct
21 Correct 585 ms 64972 KB Output is correct
22 Correct 582 ms 63112 KB Output is correct
23 Correct 606 ms 53452 KB Output is correct
24 Correct 587 ms 64548 KB Output is correct
25 Correct 1139 ms 82636 KB Output is correct
26 Correct 1254 ms 122884 KB Output is correct
27 Correct 1420 ms 108280 KB Output is correct
28 Correct 1533 ms 96956 KB Output is correct
29 Correct 1462 ms 94268 KB Output is correct
30 Correct 1407 ms 99644 KB Output is correct
31 Correct 1103 ms 67476 KB Output is correct
32 Correct 1369 ms 106696 KB Output is correct