Submission #1316922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316922		ashikur_	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	484 ms	115564 KiB

tracks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define inf (ll)1e15
#define ll long long
#define lll __int128_t
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vd vector<double>
#define mod 1000000007
// #define mod 998244353
#define pie acos(-1.0)
#define LSOne(i) ((i) & -(i))
#define EPS 1e-9
vi dr = {1, 0, -1, 0}, dc = {0, 1, 0, -1};

int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<string> vtr(n);
    for(int i = 0; i < n; i++) cin >> vtr[i];

    vector<vi> dist(n, vi(m, -1)); dist[0][0] = 1;
    deque<pi> que; que.push_back({0, 0});
    int ans = 0;

    while(que.size()){
        auto [i, j] = que.front(); que.pop_front();
        ans = max(ans, dist[i][j]);
        for(int k = 0; k < 4; k++){
            int r = i+dr[k], c = j+dc[k];
            if(r < 0 || c < 0 || r >= n || c >= m) continue;
            if(vtr[r][c] == '.' || dist[r][c] != -1) continue;

            dist[r][c] = dist[i][j];
            if(vtr[i][j] == vtr[r][c]){
                que.push_front({r, c});
            } else{
                dist[r][c]++;
                que.push_back({r, c});
            }
        }
    }
    cout << ans << "\n";
}

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