Submission #1312357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312357		RgZg_LnEn	Tracks in the Snow (BOI13_tracks)	C++20	82.50 / 100	993 ms	601464 KiB

tracks

//UPDATERA ARRAY STORLEKEN!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const ll INF=1e15;
const ll MAXN=4006;//UPDATERA ARRAY STORLEKEN!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
ll n,ans,m,dist[MAXN*MAXN];
bool already[MAXN*MAXN];
char lst[MAXN*MAXN];

int Link[MAXN*MAXN],cnt;

struct node{
    int end,next,w;
}Edge[2*MAXN*MAXN];

void insert(int x,int y,int z){
    int temp=Link[x];
    cnt++;
    Link[x]=cnt;
    Edge[cnt].next=temp;
    Edge[cnt].end=y;
    Edge[cnt].w=z;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=n*m;i++){
        cin>>lst[i];
        dist[i]=INF;
    }

    for(int i=1;i<=n*m;i++){
        if(i%m!=1&&lst[i]!='.'&&lst[i-1]!='.'){
            if(lst[i]==lst[i-1]){//need not a dot
                insert(i,i-1,0);
            }else insert(i,i-1,1);
        }

        if(i%m!=0&&lst[i]!='.'&&lst[i+1]!='.'){
            if(lst[i]==lst[i+1]){
                insert(i,i+1,0);
            }else insert(i,i+1,1);
        }

        if(i>m&&lst[i]!='.'&&lst[i-m]!='.'){
            if(lst[i]==lst[i-m]){
                insert(i,i-m,0);
            }else insert(i,i-m,1);
        }


        if(i<=n*m-m&&lst[i]!='.'&&lst[i+m]!='.'){
            if(lst[i]==lst[i+m]){
                insert(i,i+m,0);
            }else insert(i,i+m,1);
        }
    }

    deque<ll> Q;
    Q.push_back(1);
    dist[1]=0;

    while(!Q.empty()){
        ll a=Q.front();
        Q.pop_front();

        if(already[a]) continue;

        already[a]=1;

        for(int i=Link[a];i;i=Edge[i].next){
            if(dist[Edge[i].end]>dist[a]+Edge[i].w){
                dist[Edge[i].end]=dist[a]+Edge[i].w;
                if(Edge[i].w==0){
                    Q.push_front(Edge[i].end);
                }else Q.push_back(Edge[i].end);
            }
        }
    }
    

    for(int i=1;i<=n*m;i++){
        if(lst[i]!='.') ans=max(ans,dist[i]);
    }
    cout<<ans+1<<'\n';
}

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