oj.uz

Submission #96945

# Submission time Handle Problem Language Result Execution time Memory
96945 2019-02-12T20:00:19 Z dalgerok Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1805 ms 131204 KB 
#include<bits/stdc++.h>
using namespace std;




const int N = 4005, INF = 2e9, dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};




int n, m, d[N][N];
char a[N][N];

inline bool check(int x, int y){
    return 1 <= x && x <= n && 1 <= y && y <= m;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            d[i][j] = INF;
        }
    }
    deque < pair < int, int > > q;
    q.push_back(make_pair(1, 1));
    d[1][1] = 1;
    while(!q.empty()){
        int x = q.front().first,
            y = q.front().second;
        q.pop_front();
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i],
                yy = y + dy[i];
            if(check(xx, yy) && a[xx][yy] != '.'){
                int val = d[x][y] + (a[x][y] != a[xx][yy]);
                if(d[xx][yy] > val){
                    d[xx][yy] = val;
                    if(a[x][y] == a[xx][yy]){
                        q.push_front(make_pair(xx, yy));
                    }
                    else{
                        q.push_back(make_pair(xx, yy));
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i][j] != '.'){
                ans = max(ans, d[i][j]);
            }
        }
    }
    cout << ans << "\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5504 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 11 ms 5248 KB Output is correct
5 Correct 7 ms 3072 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 1168 KB Output is correct
10 Correct 6 ms 2688 KB Output is correct
11 Correct 6 ms 2132 KB Output is correct
12 Correct 8 ms 3072 KB Output is correct
13 Correct 8 ms 3072 KB Output is correct
14 Correct 6 ms 3084 KB Output is correct
15 Correct 20 ms 5532 KB Output is correct
16 Correct 19 ms 5504 KB Output is correct
17 Correct 17 ms 5504 KB Output is correct
18 Correct 14 ms 5248 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 30904 KB Output is correct
2 Correct 66 ms 17884 KB Output is correct
3 Correct 400 ms 94456 KB Output is correct
4 Correct 124 ms 33692 KB Output is correct
5 Correct 261 ms 67972 KB Output is correct
6 Correct 941 ms 108276 KB Output is correct
7 Correct 29 ms 32376 KB Output is correct
8 Correct 27 ms 30976 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 28 ms 31736 KB Output is correct
12 Correct 4 ms 1664 KB Output is correct
13 Correct 65 ms 17912 KB Output is correct
14 Correct 35 ms 12024 KB Output is correct
15 Correct 36 ms 13216 KB Output is correct
16 Correct 26 ms 6648 KB Output is correct
17 Correct 156 ms 36244 KB Output is correct
18 Correct 167 ms 35832 KB Output is correct
19 Correct 114 ms 33700 KB Output is correct
20 Correct 85 ms 31096 KB Output is correct
21 Correct 234 ms 70392 KB Output is correct
22 Correct 253 ms 68088 KB Output is correct
23 Correct 295 ms 57080 KB Output is correct
24 Correct 293 ms 69612 KB Output is correct
25 Correct 1124 ms 94600 KB Output is correct
26 Correct 695 ms 131204 KB Output is correct
27 Correct 845 ms 123148 KB Output is correct
28 Correct 975 ms 108276 KB Output is correct
29 Correct 1348 ms 108984 KB Output is correct
30 Correct 1805 ms 113312 KB Output is correct
31 Correct 552 ms 73592 KB Output is correct
32 Correct 1802 ms 112600 KB Output is correct