Submission #1157493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157493		Marco_Escandon	Maze (JOI23_ho_t3)	C++20	100 / 100	464 ms	126752 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
typedef int ll;
#define x first
#define y second
ll dx[]={1,-1,0,0};
ll dy[]={0,0,-1,1};
ll n,m,k;
vector<string> cad;
vector<vector<ll>> d,v,v3;
bool inside(pair<ll,ll> c) 
{   pair<ll,ll> a={0,0}; pair<ll,ll> b={n-1,m-1}; 
    return (a.x<=c.x&&b.x>=c.x&&a.y<=c.y&&b.y>=c.y); }
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    pair<ll,ll> inicio,fin;
    cin>>n>>m>>k>>inicio.x>>inicio.y>>fin.x>>fin.y;
    inicio.x--; inicio.y--;
    fin.x--; fin.y--;
    cad.resize(n);
    for(int i=0; i<n; i++)
        cin>>cad[i];
    d.assign(n,vector<ll>(m,1e8));
    v.assign(n,vector<ll>(m,1e8));
    v3.assign(n,vector<ll>(m,1e8));
    queue<pair<ll,ll>> q,q2,q3;
    q.push(inicio);
    d[inicio.x][inicio.y]=0;
    while(!q.empty())
    {
        // expand same component
        ll asd=d[q.front().x][q.front().y];
        while(!q.empty())
        {
            pair<ll,ll> node=q.front();q.pop();
            //cerr<<node.x<<node.y<<" ";
            for(int i=0; i<4; i++)
            {
                pair<ll,ll> node1={node.x+dx[i],node.y+dy[i]};
                if(!(inside(node1)&&d[node1.x][node1.y]==1e8)) continue;
                if(cad[node1.x][node1.y]=='.')
                {
                    d[node1.x][node1.y]=d[node.x][node.y];
                    q.push(node1);
                }
                else
                {
                    if(v[node1.x][node1.y]!=0)
                    q2.push(node1);
                    v[node1.x][node1.y]=0;
                }
            }
        }
        //vertical expand
        while(!q2.empty())
        {
            pair<ll,ll> node=q2.front();q2.pop();
            q3.push(node);
            v3[node.x][node.y]=0;
            if(v[node.x][node.y]!=k-1)
            for(int i=0; i<2; i++)
            {
                pair<ll,ll> node1={node.x+dx[i],node.y+dy[i]};
                if(!(inside(node1)&&d[node1.x][node1.y]==1e8&&v[node1.x][node1.y]==1e8)) continue;
                v[node1.x][node1.y]=v[node.x][node.y]+1;
                q2.push(node1);
            }
        }
        //horizontal expand
        while(!q3.empty())
        {
            pair<ll,ll> node=q3.front();q3.pop();
            q.push(node);
            d[node.x][node.y]=asd+1;
            if(v3[node.x][node.y]!=k-1)
            for(int i=2; i<4; i++)
            {
                pair<ll,ll> node1={node.x+dx[i],node.y+dy[i]};
                if(!(inside(node1)&&d[node1.x][node1.y]==1e8&&v3[node1.x][node1.y]==1e8)) continue;
                v3[node1.x][node1.y]=v3[node.x][node.y]+1;
                q3.push(node1);
            }
        }
    }
    cout<<d[fin.x][fin.y];
    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: 6 / 6