Submission #1347709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1347709		luuthanhdatbienhoak66	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	In queue	0 ms	0 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define _Thich_Ngu_Trua_ int main()
#define Siesta ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pii pair<ll, ll>
#define F first
#define S second
const ll N = 1000005;
const ll inf = 1e18;
const ll mod = 1e9+7;

ll n, m, pos[N], stren[N], mx = -inf, mn = inf;
vector<ll> dist(N, inf);
map<ll, vector<ll>> mp;
vector<pii> adj[N];

void djk()
{
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[0] = 0;
    pq.push({0, 0});
    while(!pq.empty())
    {
        auto [val, u] = pq.top();
        pq.pop();
        if(val != dist[u]) continue;
        for(auto [v, w]:adj[u])
        {
            if(dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    cout << (dist[1]==inf?-1:dist[1]);
}

_Thich_Ngu_Trua_
{
    if (fopen("file.inp", "r"))
    {
        freopen("file.inp", "r", stdin);
        freopen("file.out", "w", stdout);
    }
    Siesta;

    cin >> n >> m;
    for(ll i=0; i<m; i++)
    {
        cin >> pos[i] >> stren[i];
        mp[pos[i]].push_back(i);
        if(pos[i] > mx) mx = pos[i];
        if(pos[i] < mn) mn = pos[i];
    }
    for(ll i=0; i<m; i++)
    {
        ll st = pos[i];
        for(ll j=1; st+j*stren[i]<=mx; j++)
        {
            if(!mp.count(st+j*stren[i])) continue;
            for(ll v:mp[st+j*stren[i]])
            {
                adj[i].push_back({v, j});
            }
        }
        for(ll j=1; st-j*stren[i]>=mn; j++)
        {
            if(!mp.count(st-j*stren[i])) continue;
            for(ll v:mp[st-j*stren[i]])
            {
                adj[i].push_back({v, j});
            }
        }
    }
    djk();
}