Submission #1285200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285200		efeg	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	650 ms	228452 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

typedef tuple<int,int,int> iii; 

const int maxN = 4100; 
char a[maxN][maxN]; 
int dist[maxN][maxN]; 
int h,w;

int dX[] = {1,-1,0,0}; 
int dY[] = {0,0,1,-1}; 

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); 
    cin >> h >> w; 
    memset(dist,-1,sizeof(dist)); 
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++){
            cin >> a[i][j]; 
        }
    }

    auto check = [&](int i,int j){
        if (i > -1 && j > -1 && i < h && j < w && dist[i][j] == -1 && a[i][j] != '.') return true; 
        return false; 
    }; 

    deque<iii> q; 
    q.push_back({0,0,1}); 
    int mx = 0; 
    while (!q.empty()){
        int i,j,d; tie(i,j,d) = q.front(); 
        q.pop_front();  
        if (dist[i][j] != -1) continue;
        dist[i][j] = d;
        mx = max(mx,d); 

        for (int x = 0; x < 4; x++){
            int toi = i + dX[x],toj = j + dY[x]; 
            if (check(toi,toj)){
                if (a[i][j] == a[toi][toj]){
                    q.push_front({toi,toj,d}); 
                }
                else q.push_back({toi,toj,d+1}); 
            }
        }

    }

    cout << mx << endl; 

    return 0; 
}

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