Submission #1257782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257782		gohann	Tracks in the Snow (BOI13_tracks)	C++20	84.69 / 100	2101 ms	401880 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define __ ios_base::sync_with_stdio(false); cin.tie(NULL);
typedef long long ll;
#define pb push_back

const vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int main(){__
    int H, W; cin >> H >> W;
    int maxi = 1;
    char grid[H][W];
    int distance[H][W];
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            distance[i][j] = 1e9;
        }
    }

    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> grid[i][j];
        }
    }
    
    deque<vector<int>> d;
    d.push_front({0, 0, 0});
    distance[0][0] = 0;
    while(!d.empty()){
        vector<int> a = d.front();
        d.pop_front();
        int x = a[0];
        int y = a[1];
        int w = a[2];
        maxi = max(maxi, distance[x][y]);
        
        for(auto dir : directions){
            int nx = x + dir[0];
            int ny = y + dir[1];
            if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
            if(grid[nx][ny] == '.') continue;
            
            int nw = !(grid[x][y] == grid[nx][ny]);
            vector<int> u = {nx, ny, nw};
            if(distance[x][y] + nw < distance[nx][ny]){
                //cout << nx << " " << ny << "\n";
                distance[nx][ny] = distance[x][y] + nw;
                if(nw == 1){
                    d.push_back(u);
                }
                else if(nw == 0){
                    d.push_front(u);
                }
            }
        }
    }

    cout << maxi + 1;
}  

• Subtask 1: 30 / 30
• Subtask 2: 54.6875 / 70