Submission #199225

#	Time	Username	Problem	Language	Result	Execution time	Memory
199225		Alexa2001	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	226 ms	72292 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

/// 12:08

const int Nmax = 30005;
const int base = 30007;
typedef pair<int,int> Pair;

vector<int> v[Nmax];
vector<Pair> edge[Nmax];

int salt[Nmax], pos[Nmax], dist[Nmax], last[Nmax];

int n, m;

int solve(int start, int finish)
{
    priority_queue< Pair, vector<Pair>, greater<Pair> > heap;
    heap.push({0, start});

    int i;
    for(i=0; i<n; ++i) dist[i] = 1e9;
    dist[start] = 0;

    while(heap.size())
    {
        int node, dst;
        tie(dst, node) = heap.top();
        heap.pop();
        if(dist[node] != dst) continue;

        if(node == finish) return dst;

        for(auto &it : edge[node])
            if(dist[node] + it.second < dist[it.first])
            {
                dist[it.first] = dist[node] + it.second;
                heap.push({dist[it.first], it.first});
            }
    }

    return -1;
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;

    int i;
    for(i=0; i<m; ++i)
    {
        cin >> pos[i] >> salt[i];
        v[salt[i]].push_back(pos[i]);
    }

    for(i=0; i<n; ++i)
    {
        sort(v[i].begin(), v[i].end());
        v[i].erase( unique(v[i].begin(), v[i].end()) , v[i].end() );
    }

    for(i=1; i<=30000; ++i)
    {
        for(auto it : v[i]) last[it] = i;

        for(auto it : v[i])
        {
            int p, dst;
            for(p = it - i, dst = 1; p >= 0; p -= i, ++dst)
            {
                edge[it].push_back({p, dst});
                if(last[p] == i) break;
            }

            for(p = it + i, dst = 1; p<n; p += i, ++dst)
            {
                edge[it].push_back({p, dst});
                if(last[p] == i) break;
            }
        }
    }

    cout << solve(pos[0], pos[1]) << '\n';

    return 0;
}

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