Submission #1125419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125419		ASN49K	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	10 / 100	2 ms	2632 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);
    }
    queue<cord>q;
    q.push(cords[0]);
    vector<bool>viz(n,0);

    auto insert=[&](cord nextt,int cost)
    {
        if(!dist.count(nextt))
        {
            dist[nextt]=cost;
            q.push(nextt);
        }
        else if(dist[nextt]>cost)
        {
            //it's already in queue
            //can happen if delta is 0
            dist[nextt]=cost;
        }
    };
    while(q.size())
    {
        cord then=q.front();
        int then_cost=dist[then];
        q.pop();
        if(then.pos==cords[1].pos)
        {
            cout<<then_cost<<'\n';
            return 0;
        }
        //moves to nearby
        if(!viz[then.pos])
        {
            viz[then.pos]=true;
            for(auto &c:adj[then.pos])
            {
                insert((cord){then.pos , c} , then_cost);
            }
        }
        if(then.pos>=then.step)
        {
            insert({then.pos-then.step , then.step} , then_cost+1);
        }
        if(then.pos+then.step<n)
        {
            insert({then.pos+then.step , then.step} , then_cost+1);
        }
    }
    cout<<-1;
}

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