Submission #1083778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083778		altern23	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	745 ms	256852 KiB

tracks

#include <bits/stdc++.h>
#include <functional>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define sec second
#define double long double
#define debug(x) cout << #x << " = " << x << "\n";

const ll MOD = 1e9 + 7;
const ll N = 1e6 + 5;
const ll INF = 1e18;

template <typename T>
ostream& operator << (ostream& os, vector<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";

    return os;
}

template <typename T>
ostream& operator << (ostream& os, set<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";

    return os;
}

ll a[N];

ostream& operator << (ostream& os, pii x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";

    return os;
}

int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll h,w; cin >> h >> w;

        char grid[h + 5][w + 5];
        ll dist[h + 5][w + 5];

        memset(dist, 0x3f, sizeof(dist));

        dist[1][1] = 1;
        
        for(int i=1;i<=h;i++){
            for(int j=1;j<=w;j++) cin >> grid[i][j];
        }

        deque<pair<ll, pii>>dq;
        dq.push_back({1, {1, 1}});

        ll di[] = {0, 0, 1, -1}, dj[] = {1, -1, 0, 0};
        for(;!dq.empty();){
            auto x = dq.front(); dq.pop_front();
            if(x.fi > dist[x.sec.fi][x.sec.sec]) continue;

            for(int i=0;i<4;i++){
                ll newi = x.sec.fi + di[i], newj = x.sec.sec + dj[i];
                if(newi < 1 || newj < 1 || newi > h || newj > w) continue;
                if(grid[newi][newj] == '.' || dist[newi][newj] <= x.fi + (grid[newi][newj] != grid[x.sec.fi][x.sec.sec])) continue;
                dist[newi][newj] = x.fi + (grid[newi][newj] != grid[x.sec.fi][x.sec.sec]);

                if(grid[newi][newj] != grid[x.sec.fi][x.sec.sec]) dq.push_back({dist[newi][newj], {newi, newj}});
                else dq.push_front({dist[newi][newj], {newi, newj}});
            }
        }

        ll mx = 1;
        for(int i=1;i<=h;i++){
            for(int j=1;j<=w;j++){
                if(grid[i][j] != '.') mx = max(mx, dist[i][j]);
            }
        }

        cout << mx << "\n";
    }
} 

/*

*/  

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