Submission #1257791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257791		gohann	Tracks in the Snow (BOI13_tracks)	C++20	86.88 / 100	2107 ms	464680 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}};
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()){
        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]);
        if(vis[x][y]) continue;
        vis[x][y]=1;
        
        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: 56.875 / 70