oj.uz

Submission #794238

# Submission time Handle Problem Language Result Execution time Memory
794238 2023-07-26T11:19:08 Z hanlei35 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1006 ms 130844 KB 
#include <bits/stdc++.h>

using namespace std;

char grid[4000][4000];
int H, W, dist[4000][4000];
const int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0}, mx = 1e9;

int main(){
    cin >> H >> W;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin >> grid[i][j];
            
            dist[i][j] = mx;
        }
    }
    
    deque<pair<int,int>> d;
    dist[0][0] = 1;
    d.push_back({0,0});
    int ans = 0;
    
    while(!d.empty()){
        pair<int,int> curr = d.front();
        d.pop_front();
        
        ans = max(ans, dist[curr.first][curr.second]);
        for(int i=0;i<4;i++){
            int x = curr.first + dx[i], y = curr.second + dy[i];
            if(x >= 0 && x < H && y >= 0 && y < W && grid[x][y] != '.'){
                int w = grid[x][y] == grid[curr.first][curr.second] ? 0:1;
                
                if(dist[curr.first][curr.second] + w < dist[x][y]){
                    dist[x][y] = dist[curr.first][curr.second] + w;
                    
                    if(w == 0) d.push_front({x,y});
                    else d.push_back({x,y});
                }
            }
        }
    }
    
    cout << ans << "\n";
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5392 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 10 ms 5084 KB Output is correct
5 Correct 5 ms 3004 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 688 KB Output is correct
8 Correct 1 ms 692 KB Output is correct
9 Correct 1 ms 1088 KB Output is correct
10 Correct 4 ms 2588 KB Output is correct
11 Correct 3 ms 2116 KB Output is correct
12 Correct 7 ms 3028 KB Output is correct
13 Correct 5 ms 3012 KB Output is correct
14 Correct 5 ms 2900 KB Output is correct
15 Correct 16 ms 5552 KB Output is correct
16 Correct 16 ms 5316 KB Output is correct
17 Correct 17 ms 5204 KB Output is correct
18 Correct 10 ms 5180 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 30652 KB Output is correct
2 Correct 80 ms 17748 KB Output is correct
3 Correct 631 ms 94100 KB Output is correct
4 Correct 161 ms 33452 KB Output is correct
5 Correct 373 ms 67708 KB Output is correct
6 Correct 984 ms 107532 KB Output is correct
7 Correct 15 ms 32024 KB Output is correct
8 Correct 13 ms 30600 KB Output is correct
9 Correct 3 ms 572 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 13 ms 31416 KB Output is correct
12 Correct 2 ms 1600 KB Output is correct
13 Correct 77 ms 17736 KB Output is correct
14 Correct 45 ms 11952 KB Output is correct
15 Correct 43 ms 13032 KB Output is correct
16 Correct 33 ms 6604 KB Output is correct
17 Correct 197 ms 36088 KB Output is correct
18 Correct 176 ms 35544 KB Output is correct
19 Correct 159 ms 33448 KB Output is correct
20 Correct 151 ms 31048 KB Output is correct
21 Correct 371 ms 70004 KB Output is correct
22 Correct 382 ms 67852 KB Output is correct
23 Correct 377 ms 56788 KB Output is correct
24 Correct 374 ms 69376 KB Output is correct
25 Correct 769 ms 94192 KB Output is correct
26 Correct 910 ms 130844 KB Output is correct
27 Correct 904 ms 112316 KB Output is correct
28 Correct 964 ms 107432 KB Output is correct
29 Correct 1006 ms 105216 KB Output is correct
30 Correct 960 ms 109588 KB Output is correct
31 Correct 640 ms 73400 KB Output is correct
32 Correct 972 ms 111080 KB Output is correct