제출 #1137805

#제출 시각아이디문제언어결과실행 시간메모리
1137805Muhammad_AneeqText editor (CEOI24_editor)C++20
45 / 100
4078 ms278864 KiB
/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <set>
#include <map>
#include <queue>
#warning check the output
using namespace std;
int const N=1e6+10;
int n;
int a[N]={};
map<pair<int,int>,int>vals;
void bfs(int i,int j)
{
    set<pair<int,pair<int,int>>>Q;
    Q.insert({0,{i,j}});
    while (Q.size())
    {
        int x,y;
        tie(x,y)=(*begin(Q)).second;
        int c=(*begin(Q)).first;
        Q.erase(begin(Q));
        if (vals[{x,y}]!=c)
            continue;
        int x1=x-1,y1=y;
        if (x1>0)
        {
            y1=min(y,a[x1]+1);
            if (vals.find({x1,y1})==vals.end())
                vals[{x1,y1}]=2e9+10;
            if (vals[{x1,y1}]>vals[{x,y}]+1)
            {
                vals[{x1,y1}]=vals[{x,y}]+1;
                Q.insert({vals[{x1,y1}],{x1,y1}});
            }
        }
        x1=x+1,y1=y;
        if (x1<=n)
        {
            y1=min(y1,a[x1]+1);
            if (vals.find({x1,y1})==vals.end())
                vals[{x1,y1}]=2e9+10;
            if (vals[{x1,y1}]>vals[{x,y}]+1)
            {
                vals[{x1,y1}]=vals[{x,y}]+1;
                Q.insert({vals[{x1,y1}],{x1,y1}});
            }
        }
        x1=x+1,y1=1;
        if (x1<=n)
        {
            if (vals.find({x1,y1})==vals.end())
                vals[{x1,y1}]=2e9+10;
            if (vals[{x1,y1}]>vals[{x,y}]+a[x]+2-y)
            {
                vals[{x1,y1}]=vals[{x,y}]+a[x]-y+2;
                Q.insert({vals[{x1,y1}],{x1,y1}});
            }
        }
        x1=x-1;
        if(x1>0)
        {
            y1=a[x1]+1;
            if (vals.find({x1,y1})==vals.end())
                vals[{x1,y1}]=2e9+10;
            if (vals[{x1,y1}]>vals[{x,y}]+y)
            {
                vals[{x1,y1}]=vals[{x,y}]+y;
                Q.insert({vals[{x1,y1}],{x1,y1}});
            }
        }
    }
}
int sl,sc;
int el,ec;
inline void solve()
{
    cin>>n;
    cin>>sl>>sc;
    cin>>el>>ec;
    vals[{sl,sc}]=0;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    bfs(sl,sc);
    int ans=2e9+10;
    for (auto i:vals)
    {
        int x,y;
        tie(x,y)=i.first;
        if (el!=x)
            continue;
        ans=min(ans,abs(el-x)+abs(ec-y)+i.second);
    }
    cout<<ans<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:11:2: warning: #warning check the output [-Wcpp]
   11 | #warning check the output
      |  ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...