oj.uz

답안 #1029856

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1029856 2024-07-21T12:27:07 Z VectorLi Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 629 ms 130896 KB 
#include <bits/stdc++.h>
#define long long long

using namespace std;

const int N = 4000;
const int B = numeric_limits<int>::max();
const int X[4] = {0, 0, 1, -1}, Y[4] = {1, -1, 0, 0};

int n, m;
string a[N];

deque<pair<int, int>> q;
int d[N][N];

bool valid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && a[x][y] != '.';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    q.push_back({0, 0});
    for (int i = 0; i < n; i++) {
        fill(d[i], d[i] + m, B);
    }
    d[0][0] = 0;

    int c = 0;
    while (not q.empty()) {
        int x0, y0;
        tie(x0, y0) = q.front();
        q.pop_front();
        c = max(c, d[x0][y0]);
        for (int i = 0; i < 4; i++) {
            int x1 = x0 + X[i], y1 = y0 + Y[i];
            if (valid(x1, y1) && d[x1][y1] > d[x0][y0] + (a[x0][y0] != a[x1][y1])) {
                d[x1][y1] = d[x0][y0] + (a[x0][y0] != a[x1][y1]);
                if (a[x0][y0] == a[x1][y1]) {
                    q.push_front({x1, y1});
                } else {
                    q.push_back({x1, y1});
                }
            }
        }
    }
    cout << c + 1 << "\n";

    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 4024 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 6 ms 3676 KB Output is correct
5 Correct 2 ms 2140 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 2 ms 864 KB Output is correct
10 Correct 2 ms 1880 KB Output is correct
11 Correct 2 ms 1680 KB Output is correct
12 Correct 4 ms 2276 KB Output is correct
13 Correct 2 ms 2136 KB Output is correct
14 Correct 2 ms 2224 KB Output is correct
15 Correct 7 ms 4140 KB Output is correct
16 Correct 10 ms 3996 KB Output is correct
17 Correct 6 ms 3864 KB Output is correct
18 Correct 4 ms 3712 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15960 KB Output is correct
2 Correct 41 ms 14884 KB Output is correct
3 Correct 212 ms 96520 KB Output is correct
4 Correct 66 ms 30372 KB Output is correct
5 Correct 161 ms 65864 KB Output is correct
6 Correct 629 ms 109676 KB Output is correct
7 Correct 9 ms 16732 KB Output is correct
8 Correct 9 ms 15960 KB Output is correct
9 Correct 2 ms 872 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 10 ms 16220 KB Output is correct
12 Correct 2 ms 1108 KB Output is correct
13 Correct 44 ms 14876 KB Output is correct
14 Correct 25 ms 9644 KB Output is correct
15 Correct 19 ms 10524 KB Output is correct
16 Correct 20 ms 6224 KB Output is correct
17 Correct 105 ms 32824 KB Output is correct
18 Correct 65 ms 32284 KB Output is correct
19 Correct 63 ms 30376 KB Output is correct
20 Correct 56 ms 28056 KB Output is correct
21 Correct 128 ms 68284 KB Output is correct
22 Correct 138 ms 66092 KB Output is correct
23 Correct 149 ms 55520 KB Output is correct
24 Correct 113 ms 67132 KB Output is correct
25 Correct 275 ms 96524 KB Output is correct
26 Correct 473 ms 130896 KB Output is correct
27 Correct 427 ms 114512 KB Output is correct
28 Correct 545 ms 109804 KB Output is correct
29 Correct 583 ms 107460 KB Output is correct
30 Correct 558 ms 111784 KB Output is correct
31 Correct 434 ms 72240 KB Output is correct
32 Correct 470 ms 113412 KB Output is correct