제출 #452101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
452101		ZaZo_	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	358 ms	64188 KiB

skyscraper

//Sorry but iam targeting IOI :))
//NEVER LOSE HOPE
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define endl "\n"
#define ceil(a,b)   (a+(b-1))/b
#define all(v) v.begin(),v.end()
#define Hidden ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N=3e4+10,mod = 1e9+7;
int n,m,f[N],dis[N];
pair<int,int>a[N];
vector<pair<int,int>>adj[N];
set<pair<int,int>>vis;
int main(){
    cin>>n>>m;
    for(int i=0;i<m;++i){
        cin>>a[i].first>>a[i].second;
        vis.insert({a[i].first,a[i].second});
    }
    for(auto i:vis){
        for(int j=i.first+i.second;j<n;j+=i.second){
            adj[i.first].push_back({j,((j-i.first)/i.second)});
            if(vis.find({j,i.second})!=vis.end()) break;
        }
    }
    for(auto i:vis){
        for(int j=i.first-i.second;j>=0;j-=i.second){
            adj[i.first].push_back({j,((i.first-j)/i.second)});
            if(vis.find({j,i.second})!=vis.end()) break;
        }
    }
    priority_queue<pair<int,int>>pq;
    pq.push({0,a[0].first});
    for(int i=0;i<N;++i) dis[i]=INT_MAX;
    dis[a[0].first]=0;
    while(!pq.empty()){
        pair<int,int>p=pq.top();
        pq.pop();
        int u=p.second;
        for(auto i:adj[u]){
            int cost=dis[u]+i.second;
            if(cost<dis[i.first]){
                dis[i.first]=cost;
                pq.push({-cost,i.first});
            }
        }
    }
    if(dis[a[1].first]==INT_MAX) cout<<"-1\n";
    else cout<<dis[a[1].first]<<'\n';
 
    
 
 
}
    

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