Submission #1125436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125436		ASN49K	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1097 ms	52532 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define pb push_back
#define bug(a) std::cerr << "(" << #a << ": " << a << ")\n";

using i64 = long long;

const int N=100'000;
struct cord
{
    int pos,step;
    bool operator <(const cord &b)const
    {
        if(pos==b.pos)
        {
            return step<b.step;
        }
        return pos<b.pos;
    }
    bool operator ==(const cord &b)const
    {
        return pos==b.pos && step==b.step;
    }
};
map<cord , int>dist;
vector<int>adj[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector<cord>cords(m);
    for(auto &c:cords)
    {
        cin>>c.pos>>c.step;
        adj[c.pos].push_back(c.step);
    }
    deque<cord>q;
    q.push_front(cords[0]);
    vector<bool>viz(n,0);

    auto insert=[&](cord nextt,int cost,bool fronted)
    {
        if(!dist.count(nextt) || dist[nextt]>cost)
        {
            dist[nextt]=cost;
            if(fronted)
            {
                q.push_front(nextt);
            }
            else
            {
                q.push_back(nextt);
            }
        }
    };
    while(q.size())
    {
        assert(dist.size()<=6'000'000);
        cord then=q.front();
        int then_cost=dist[then];
        q.pop_front();
        if(then.pos==cords[1].pos)
        {
            cout<<then_cost<<'\n';
            return 0;
        }


        if(!viz[then.pos])
        {
            viz[then.pos]=true;
            for(auto &c:adj[then.pos])
            {
                insert((cord){then.pos , c} , then_cost , true);
            }
            adj[then.pos].clear();
        }
        if(then.pos>=then.step)
        {
            insert({then.pos-then.step , then.step} , then_cost+1 , false);
        }
        if(then.pos+then.step<n)
        {
            insert({then.pos+then.step , then.step} , then_cost+1 , false);
        }
    }
    cout<<-1;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43