Submission #1099344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099344		theSkeleton	Tracks in the Snow (BOI13_tracks)	C++17	89.06 / 100	2105 ms	246356 KiB

tracks

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define space <<' '<<
#define endl '\n'
#define inf 1e14
#define F first
#define S second
#define PB push_back
#define PF push_front
#define md(a) ((a+mod)%mod)
#define MP(a,b) make_pair(a,b)
#define MT(a,b,c) make_tuple(a,b,c)
typedef long long ll;
using namespace std;
template<typename t> using heap=
priority_queue<t,vector<t>,greater<t>>;
const ll mx = 4005;
ll D[mx][mx];
char s[mx][mx];
bool seen[mx][mx];
set<pair<ll,pair<ll,ll>>> l;
pair<ll,ll> n[]={MP(0,1),MP(0,-1),MP(1,0),MP(-1,0)};
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll h,w;cin>>h>>w;
    for(ll i=0;i<h;i++)
        for(ll j=0;j<w;j++){
            cin>>s[i][j];
            D[i][j]=2e7;
        }
    ll o=0;
    D[0][0]=1;
    l.insert(MP(1,MP(0,0)));
    if(s[0][0]=='.'){
        cout<<0;
        return 0;
    }
    while(!l.empty()){
        auto d=l.begin()->S;
        l.erase(l.begin());
        if(seen[d.F][d.S])
            continue;
        seen[d.F][d.S]=1;
        o=max(o,D[d.F][d.S]);
        for(ll p,x,y,i=0;i<4;i++){
            x=d.F+n[i].F,y=d.S+n[i].S;
            if(0<=x&&x<h&&0<=y&&y<w)
            if(s[x][y]!='.'){
                p=s[d.F][d.S]!=s[x][y];
                if(D[d.F][d.S]+p<D[x][y]){
                    D[x][y]=D[d.F][d.S]+p;
                    l.insert(MP(D[x][y],MP(x,y)));
                }
            } 
        }
    }
    cout<<o;
    return 0;
}

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