Submission #1321785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321785		NValchanov	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	613 ms	3500 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

typedef long long llong;

const int MAXN = 3e4 + 10;
const int INF = 1e9 + 10;

struct Edge
{
    int to, cost;

    Edge(){};

    Edge(int to, int cost)
    {
        this->to = to;
        this->cost = cost;
    }

    friend bool operator<(const Edge &e1, const Edge &e2)
    {
        return e1.cost > e2.cost;
    }
};

int n, m;
int start, finish;
int p[MAXN];
int power[MAXN];
int dist[MAXN];
vector < int > poss[MAXN];

void read()
{
    cin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        cin >> p[i] >> power[i];

        p[i]++;
    }

    start = p[1];
    finish = p[2];

    for(int i = 1; i <= m; i++)
    {
        poss[p[i]].push_back(power[i]);
    }
}

void solve()
{
    for(int i = 1; i <= n; i++)
    {
        dist[i] = INF;
    }

    priority_queue < Edge > pq;

    dist[start] = 0;

    pq.push(Edge(start, 0));

    while(!pq.empty())
    {
        Edge t = pq.top();
        pq.pop();

        int u = t.to;

        if(t.cost > dist[u])
            continue;

        for(int len : poss[u])
        {
            for(int jumps = 1; u + len * jumps <= n; jumps++)
            {
                int v = u + len * jumps;

                if(dist[u] + jumps < dist[v])
                {
                    dist[v] = dist[u] + jumps;

                    pq.push(Edge(v, dist[v]));
                }
            }

            for(int jumps = 1; u - len * jumps >= 1; jumps++)
            {
                int v = u - len * jumps;

                if(dist[u] + jumps < dist[v])
                {
                    dist[v] = dist[u] + jumps;

                    pq.push(Edge(v, dist[v]));
                }
            }
        }
    }

    if(dist[finish] == INF)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << dist[finish] << endl;
    }
}

int main()
{
    speed();
    read();
    solve();

	return 0;
}

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