Submission #889120

#	Time	Username	Problem	Language	Result	Execution time	Memory
889120		Maite_Morale	Maze (JOI23_ho_t3)	C++14	94 / 100	2073 ms	274244 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;
    ppp inv(ppp h){
        h.F.F.F*=-1;h.F.F.S*=-1;
        h.F.S.F*=-1;h.F.S.S*=-1;
    return h;
    }
    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(inv({{{0,k},{k,k}},s}));  
        while(!q.empty()){
            ppp u=inv(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;a[u.S.X][u.S.Y]='*';
            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(inv(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=max(w.F.S.F,w.F.S.S);
                q.push(inv(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: 8 / 8
• Subtask 8: 0 / 6