oj.uz

답안 #1120086

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1120086 2024-11-28T00:53:55 Z usacoplat Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1031 ms 222540 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n';
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;

char grid[4000][4000];
int dist[4000][4000];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    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;
        }
    }
    deque<array<int, 3>> q;
    q.push_back({0, 0, 1});
    while (!q.empty()) {
        array<int, 3> s = q.front();
        q.pop_front();
        dist[s[0]][s[1]] = min(s[2], dist[s[0]][s[1]]);
        if (s[0] > 0) {
            if (grid[s[0]-1][s[1]] != '.') {
                if (grid[s[0]-1][s[1]] == grid[s[0]][s[1]]) {
                    if (dist[s[0]-1][s[1]] > s[2]) {
                        q.push_front({s[0]-1, s[1], s[2]});
                    }
                } else {
                    if (dist[s[0]-1][s[1]] > s[2]+1) {
                        q.push_back({s[0]-1, s[1], s[2]+1});
                    }
                }
            }
        }
        if (s[0] < n-1) {
            if (grid[s[0]+1][s[1]] != '.') {
                if (grid[s[0]+1][s[1]] == grid[s[0]][s[1]]) {
                    if (dist[s[0]+1][s[1]] > s[2]) {
                        q.push_front({s[0]+1, s[1], s[2]});
                    }
                } else {
                    if (dist[s[0]+1][s[1]] > s[2]+1) {
                        q.push_back({s[0]+1, s[1], s[2]+1});
                    }
                }
            }
        }
        if (s[1] > 0) {
            if (grid[s[0]][s[1]-1] != '.') {
                if (grid[s[0]][s[1]-1] == grid[s[0]][s[1]]) {
                    if (dist[s[0]][s[1]-1] > s[2]) {
                        q.push_front({s[0], s[1]-1, s[2]});
                    }
                } else {
                    if (dist[s[0]][s[1]-1] > s[2]+1) {
                        q.push_back({s[0], s[1]-1, s[2]+1});
                    }
                }
            }
        }
        if (s[1] < m-1) {
            if (grid[s[0]][s[1]+1] != '.') {
                if (grid[s[0]][s[1]+1] == grid[s[0]][s[1]]) {
                    if (dist[s[0]][s[1]+1] > s[2]) {
                        q.push_front({s[0], s[1]+1, s[2]});
                    }
                } else {
                    if (dist[s[0]][s[1]+1] > s[2]+1) {
                        q.push_back({s[0], s[1]+1, s[2]+1});
                    }
                }
            }
        }
    }
    int out = 0;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            if (dist[i][j] < 1e9) {
                out = max(out, dist[i][j]);
            }
        }
    }
    cout << out << endl;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 12880 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 11 ms 13552 KB Output is correct
5 Correct 5 ms 8528 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 3 ms 6480 KB Output is correct
11 Correct 4 ms 6736 KB Output is correct
12 Correct 9 ms 8784 KB Output is correct
13 Correct 4 ms 8528 KB Output is correct
14 Correct 4 ms 8528 KB Output is correct
15 Correct 16 ms 12880 KB Output is correct
16 Correct 19 ms 12880 KB Output is correct
17 Correct 12 ms 12880 KB Output is correct
18 Correct 12 ms 13392 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 78416 KB Output is correct
2 Correct 56 ms 27244 KB Output is correct
3 Correct 300 ms 78756 KB Output is correct
4 Correct 85 ms 41544 KB Output is correct
5 Correct 168 ms 62024 KB Output is correct
6 Correct 1031 ms 128236 KB Output is correct
7 Correct 8 ms 78416 KB Output is correct
8 Correct 9 ms 78416 KB Output is correct
9 Correct 3 ms 4688 KB Output is correct
10 Correct 1 ms 2640 KB Output is correct
11 Correct 9 ms 78416 KB Output is correct
12 Correct 2 ms 6480 KB Output is correct
13 Correct 60 ms 27216 KB Output is correct
14 Correct 31 ms 21072 KB Output is correct
15 Correct 17 ms 23124 KB Output is correct
16 Correct 31 ms 10912 KB Output is correct
17 Correct 146 ms 43636 KB Output is correct
18 Correct 67 ms 43592 KB Output is correct
19 Correct 86 ms 41568 KB Output is correct
20 Correct 74 ms 37536 KB Output is correct
21 Correct 183 ms 64184 KB Output is correct
22 Correct 162 ms 62144 KB Output is correct
23 Correct 259 ms 52044 KB Output is correct
24 Correct 144 ms 64172 KB Output is correct
25 Correct 234 ms 78664 KB Output is correct
26 Correct 609 ms 222540 KB Output is correct
27 Correct 693 ms 117652 KB Output is correct
28 Correct 918 ms 128224 KB Output is correct
29 Correct 975 ms 123116 KB Output is correct
30 Correct 820 ms 132232 KB Output is correct
31 Correct 905 ms 68004 KB Output is correct
32 Correct 696 ms 124812 KB Output is correct