제출 #250961

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250961		eohomegrownapps	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	1 ms	384 KiB

skyscraper

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<vector<ll>> smallpowers; //on given skyscraper
vector<vector<pair<ll,ll>>> adjlist; //weight, node

ll n;

ll INF = 1e18;

ll dijkstra(ll startloc, ll endloc){
    ll start = startloc;
    vector<vector<ll>> distances(n, vector<ll>(ll(sqrt(n))+1, INF));
    distances[start][0]=0;
    priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,less<pair<ll,pair<ll,ll>>>> pq;
    pq.push({0,{0,0}});
    while (pq.size()>0){
        auto f = pq.top();
        pq.pop();
        if (distances[f.second.first][f.second.second]<f.first){
            continue;
        }
        ll curdist = f.first;
        ll curnode = f.second.first;
        ll curind = f.second.second;
        if (curind==0){
            // we can go to a doge with cost 0
            for (ll i : smallpowers[curnode]){
                if (distances[curnode][i]>curdist){
                    distances[curnode][i]=curdist;
                    pq.push({distances[curnode][i],{curnode,i}});
                }
            }
            // or we can jump skyscrapers
            for (auto p : adjlist[curnode]){
                if (distances[p.second][0]>curdist+p.first){
                    distances[p.second][0]=curdist+p.first;
                    pq.push({distances[p.second][0],{p.second,0}});
                }
            }
        } else {
            //we can go to central node with cost 0
            if (distances[curnode][0]>curdist){
                distances[curnode][0]=curdist;
                pq.push({distances[curnode][0],{curnode,0}});
            }
            //or we can go to an adjacent node
            if (curnode-curind>=0&&distances[curnode-curind][curind]>curdist+1){
                distances[curnode-curind][curind]=curdist+1;
                pq.push({distances[curnode-curind][curind],{curnode-curind,curind}});
            }
            if (curnode+curind<n&&distances[curnode+curind][curind]>curdist+1){
                distances[curnode+curind][curind]=curdist+1;
                pq.push({distances[curnode+curind][curind],{curnode+curind,curind}});
            }
        }
    }
    return distances[endloc][0];
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    ll m;
    cin>>n>>m;
    ll sqrtv = sqrt(n);
    smallpowers.resize(n);
    adjlist.resize(n);
    ll startloc = 0;
    ll endloc = 0;
    for (ll i = 0; i<m; i++){
        ll b,p;
        cin>>b>>p;
        if (i==0){
            startloc=b;
        } 
        if (i==1){
            endloc=b;
        }
        //skyscraper b, moves p
        if (p<sqrtv){
            smallpowers[b].push_back(p);
        } else {
            ll cnt = 0;
            for (ll x = b+p; x<n; x+=p){
                cnt++;
                adjlist[b].push_back({cnt,x});
            } 
            cnt = 0;
            for (ll x = b-p; x>=0; x-=p){
                cnt++;
                adjlist[b].push_back({cnt,x});
            }
        }
    }
    ll d = dijkstra(startloc,endloc);
    if (d==INF){
        cout<<-1<<'\n';
    } else {
        cout<<d<<'\n';
    }
}

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