Submission #889115

#	Time	Username	Problem	Language	Result	Execution time	Memory
889115		Maite_Morale	Maze (JOI23_ho_t3)	C++14	86 / 100	2081 ms	247016 KiB

Main

#include<bits/stdc++.h>
#define F first
#define S second
#define X first
#define Y second
#define MAX 6000005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef int ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
#define ppp pair<pair<pll,pll>,pll>

pll d[4]={{0,1},{0,-1},{1,0},{-1,0}},s,e;
string a[MAX],asd;ll m,k,n;
int main(){
    fast_in
    cin>>n>>m>>k>>s.X>>s.Y>>e.X>>e.Y;
    ll pass[n+5][m+5];
    for(int i=0;i<=m+1;i++){
        a[0]+='*';a[n+1]='*';
    }
    for(int i=1;i<=n;i++){
        cin>>asd;
        a[i]+='*';a[i]+=asd;a[i]+='*';
        for(int j=0;j<=m+1;j++)pass[i][j]=-1;
    }
    priority_queue<ppp> q;
    q.push({{{0,-k},{-k,-k}},s});  
    while(!q.empty()){
        ppp u=q.top();q.pop();
        if(pass[u.S.X][u.S.Y]!=-1)continue;
        if(u.S.X==e.X && u.S.Y==e.Y){cout<<-u.F.F.F;return 0;}
        // cout<<u.S.X<<" "<<u.S.Y<<" "<<u.F.F.F<<" "<<u.F.F.S<<" "<<u.F.S.F<<" "<<u.F.S.S<<"\n";
        pass[u.S.X][u.S.Y]=-u.F.F.F;
        for(int i=0;i<4;i++){
            pll w1={u.S.X+d[i].F,u.S.Y+d[i].S};
            if(a[w1.X][w1.Y]=='*')continue;
            ppp w={u.F,w1};
            if(-w.F.F.S==k){
                if(a[w1.X][w1.Y]=='.'){
                    q.push(w);continue;
                }
                //  cout<<w1.X<<" "<<w1.Y<<"\n";
                w.F={{w.F.F.F-1,0},{0,0}};
            }
            w.F.S.F-=abs(d[i].F);
            w.F.S.S-=abs(d[i].S);
            w.F.F.S=min(w.F.S.F,w.F.S.S);
            q.push(w);
        }
    }
return 0;
}

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