Submission #1124039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124039		kustizus	Tracks in the Snow (BOI13_tracks)	C++20	89.06 / 100	2101 ms	173664 KiB

tracks

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

#define fi first
#define se second
#define sz(s) (int)s.size()
#define bit(i, j) ((j >> i) & 1)
#define all(v) v.begin(), v.end()
#define taskname "file"

typedef long long ll;

const int N = 4e3;
int n, m, d[N + 5][N + 5];
char a[N + 5][N + 5];
bool vs[N + 5][N + 5];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
struct node{
    int val, x, y;
};
struct cmp{
    bool operator()(node a, node b){
        return a.val > b.val;
    }
};
priority_queue <node, vector<node>, cmp> pq;

void solve(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];
    d[1][1] = 1;
    vs[1][1] = true;
    pq.push({1, 1, 1});
    int ans = 0;
    while (sz(pq)){
        node x = pq.top();
        pq.pop();
        ans = max(ans, x.val);
        for (int k = 0; k < 4; ++k){
            int i = x.x + dx[k];
            int j = x.y + dy[k];
            if (i < 1 || i > n || j < 1 || j > m) continue;
            if (vs[i][j]) continue;
            if (a[i][j] == '.') continue;
            vs[i][j] = true;
            d[i][j] = x.val + (a[i][j] != a[x.x][x.y]);
            pq.push({d[i][j], i, j});
        }
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen(taskname".inp", "r", stdin);
    // freopen(taskname".out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
}

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