Submission #1156211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156211		irmuun	Maze (JOI23_ho_t3)	C++20	19 / 100	2098 ms	174604 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

ll r,c,n;
ll sr,sc;
ll gr,gc;

vector<vector<ll>>g,dist;
vector<vector<char>>s;
vector<ll>adj,ans;

vector<ll>dx={0,0,-1,1};
vector<ll>dy={-1,1,0,0};

ll G=0;//group number

void dfs(ll x,ll y){
    for(ll k=0;k<4;k++){
        ll nx=x+dx[k],ny=y+dy[k];
        if(nx<1||ny<1||nx>r||ny>c||s[nx][ny]=='#'||g[nx][ny]!=0) continue;
        g[nx][ny]=G;
        dfs(nx,ny);
    }
}

ll calc(ll x,ll y){
    if(x>y) swap(x,y);
    ll lo=0,hi=r*c;
    while(lo<hi){
        ll mid=(lo+hi)/2;
        ll sum=(n*mid+1)+(mid*n-mid);
        if(x+y<=sum&&y<=n*mid+1){
            hi=mid;
        }
        else{
            lo=mid+1;
        }
    }
    return lo;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>r>>c>>n;
    cin>>sr>>sc;
    cin>>gr>>gc;
    s.resize(r+1);
    for(ll i=1;i<=r;i++){
        s[i].resize(c+1);
        for(ll j=1;j<=c;j++){
            cin>>s[i][j];
        }
    }
    g.resize(r+1);
    for(ll i=1;i<=r;i++){
        g[i].resize(c+1);
    }
    for(ll i=1;i<=r;i++){
        for(ll j=1;j<=c;j++){
            if(g[i][j]==0&&s[i][j]=='.'){
                G++;
                g[i][j]=G;
                dfs(i,j);
            }
        }
    }
    ans.resize(G+1);
    fill(all(ans),1e9);
    dist.resize(G+1);
    for(ll i=1;i<=G;i++){
        dist[i].resize(G+1);
        fill(all(dist[i]),1e9);
    }
    for(ll i=1;i<=r;i++){
        for(ll j=1;j<=c;j++){
            for(ll x=1;x<=r;x++){
                for(ll y=1;y<=c;y++){
                    if(g[i][j]==0||g[x][y]==0||g[i][j]==g[x][y]) continue;
                    ll f=calc(abs(i-x),abs(j-y));
                    ll g1=g[i][j],g2=g[x][y];
                    dist[g1][g2]=min(dist[g1][g2],f);
                    dist[g2][g1]=min(dist[g2][g1],f);
                }
            }
        }
    }
    for(ll i=1;i<=G;i++){
        for(ll j=1;j<=G;j++){
            if(dist[i][j]==1e9) dist[i][j]=0;
        }
    }
    ans[g[sr][sc]]=0;
    set<array<ll,2>>q;
    q.insert({0,g[sr][sc]});
    while(!q.empty()){
        auto [L,x]=*q.begin();
        q.erase(q.begin());
        if(ans[x]!=L) continue;
        for(ll y=1;y<=G;y++){
            if(ans[x]+dist[x][y]<ans[y]){
                ans[y]=ans[x]+dist[x][y];
                q.insert({ans[y],y});
            }
        }
    }
    cout<<ans[g[gr][gc]];
}

• Subtask 1: 0 / 8
• Subtask 2: 19 / 19
• Subtask 3: 0 / 16
• Subtask 4: 0 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6