oj.uz

답안 #1000181

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1000181 2024-06-16T23:13:28 Z a5a7 Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 311 ms 219732 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> 
using indexedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    char grid[n][m];
    ll dist[n][m];
    int visited[n][m];
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> grid[i][j];
            dist[i][j] = 1e18;
            visited[i][j] = 0;
        }
    }
    deque<pair<int, int>> q;
    dist[0][0] = 0;
    q.push_back({0, 0});
    vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    while (!q.empty()){
        auto x = q.front();
        q.pop_back();
        if (visited[x.first][x.second]) continue;
        visited[x.first][x.second] = 1;
        for (auto y : dir){
            int nx = x.first + y.first;
            int ny = x.second + y.second;
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (grid[nx][ny] == '.') continue;
            int d = grid[nx][ny] == grid[x.first][x.second] ? 0 : 1;
            if (dist[nx][ny] > (d+dist[x.first][x.second])){
                dist[nx][ny] = d+dist[x.first][x.second];
                if (d == 0){
                    q.push_front({nx, ny});
                }else{
                    q.push_back({nx, ny});
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if (dist[i][j] == 1e18) continue;
            ans = max(ans, dist[i][j]);
        }
    }
    cout << (ans+1) << endl;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3748 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 2 ms 2556 KB Output isn't correct
5 Incorrect 1 ms 1372 KB Output isn't correct
6 Incorrect 0 ms 464 KB Output isn't correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Incorrect 1 ms 1116 KB Output isn't correct
11 Incorrect 1 ms 1112 KB Output isn't correct
12 Incorrect 1 ms 1628 KB Output isn't correct
13 Incorrect 1 ms 1372 KB Output isn't correct
14 Incorrect 1 ms 1372 KB Output isn't correct
15 Incorrect 4 ms 3796 KB Output isn't correct
16 Incorrect 4 ms 3676 KB Output isn't correct
17 Incorrect 4 ms 3536 KB Output isn't correct
18 Incorrect 2 ms 2392 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1116 KB Output isn't correct
2 Incorrect 23 ms 21852 KB Output isn't correct
3 Incorrect 235 ms 219576 KB Output isn't correct
4 Incorrect 55 ms 51536 KB Output isn't correct
5 Incorrect 131 ms 123476 KB Output isn't correct
6 Incorrect 244 ms 219476 KB Output isn't correct
7 Incorrect 1 ms 860 KB Output isn't correct
8 Incorrect 1 ms 1116 KB Output isn't correct
9 Incorrect 1 ms 1116 KB Output isn't correct
10 Incorrect 1 ms 856 KB Output isn't correct
11 Incorrect 1 ms 860 KB Output isn't correct
12 Incorrect 1 ms 604 KB Output isn't correct
13 Incorrect 23 ms 21848 KB Output isn't correct
14 Incorrect 15 ms 12636 KB Output isn't correct
15 Incorrect 15 ms 13948 KB Output isn't correct
16 Incorrect 10 ms 9052 KB Output isn't correct
17 Incorrect 66 ms 56400 KB Output isn't correct
18 Incorrect 58 ms 55120 KB Output isn't correct
19 Incorrect 57 ms 51556 KB Output isn't correct
20 Incorrect 51 ms 47440 KB Output isn't correct
21 Incorrect 132 ms 127828 KB Output isn't correct
22 Incorrect 163 ms 123476 KB Output isn't correct
23 Incorrect 126 ms 106352 KB Output isn't correct
24 Incorrect 126 ms 124752 KB Output isn't correct
25 Incorrect 234 ms 219728 KB Output isn't correct
26 Correct 311 ms 218532 KB Output is correct
27 Incorrect 228 ms 219732 KB Output isn't correct
28 Incorrect 236 ms 219476 KB Output isn't correct
29 Incorrect 282 ms 219472 KB Output isn't correct
30 Incorrect 223 ms 214868 KB Output isn't correct
31 Incorrect 145 ms 140628 KB Output isn't correct
32 Incorrect 227 ms 219504 KB Output isn't correct