제출 #1015809

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015809		lucascgar	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	468 ms	155284 KiB

tracks

#include <bits/stdc++.h>

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

/*
two puddles of the same type are intersected by one with connection to start, then its all 2 animals only

começo no início
    - tudo q eu percorrer é 1 bicho só, todos os diferentes adjacentes a ele são do mesmo bicho só, e assim por diante

*/

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // overclock random

typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

const int MAXN = 4e3+12;


char g[MAXN][MAXN];

int d[MAXN][MAXN], aux[4] = {1, -1, 0, 0};

signed main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    // cout << fixed << setprecision(12);

    int n, m;
    cin >> n >> m;
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++){
        cin >> g[i][j];
        d[i][j] = 1e9;
        if (g[i][j] == '.') d[i][j] = -1;
    }

    // priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<>> q;

    deque<pair<int, pii>> q;

    q.push_back({1, {1,1}});
    d[1][1] = 1;
    int ans=1;

    while (!q.empty()){
        auto u = q.front();
        q.pop_front();

        if (u.first != d[u.second.first][u.second.second]) continue;
        
        if (u.first>ans) ans=u.first;
        pii x = u.second;
        char t = g[x.first][x.second];

        for (int a=0,b=3;a<4;a++,b--){
            int ni = x.first+aux[a],nj=x.second+aux[b];
            if (d[ni][nj] == -1) continue;

            int nd = u.first + (t != g[ni][nj]);

            if (d[ni][nj] <= nd) continue;

            d[ni][nj] = nd;

            if (nd == u.first) q.push_front({nd, {ni,nj}});
            else q.push_back({nd, {ni, nj}});
        }

    }

    cout << ans << "\n";

    return 0;
}

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