Submission #1257794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257794		gohann	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1304 ms	464712 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 di[4] = {1,0,-1,0};
int dj[4] = {0,-1,0,1};

vector<vector<int>> vis(4001,vector<int>(4001));

int main(){__
    int H, W; cin >> H >> W;
    int operations = 0;
    int maxi = 0;
    vector<string> grid(H);
    for (int i = 0; i < H; i++) cin >> grid[i];
    vector<vector<int>> distance(H, vector<int>(W, 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()){
        int x = d.front()[0];
        int y = d.front()[1];
        int w = d.front()[2];
        d.pop_front();  
        maxi = max(maxi, distance[x][y]);
        if(vis[x][y]) continue;
        vis[x][y]=1;
        
        for(int i=0;i<4;i++){
            int nx = x + di[i];
            int ny = y + dj[i];
            if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
            if(grid[nx][ny] == '.') continue;
            
            int nw = !(grid[x][y] == grid[nx][ny]);
            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({nx, ny, nw});
                }
                else if(nw == 0){
                    d.push_front({nx, ny, nw});
                }
            }
        }
    }

    cout << maxi + 1;
}  

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