Submission #452093

#	Time	Username	Problem	Language	Result	Execution time	Memory
452093		Sarah_Mokhtar	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1092 ms	189632 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];
set<pair<int,int>>adj[N];
int main(){
    cin>>n>>m;
    for(int i=0;i<m;++i){
        cin>>a[i].first>>a[i].second;
        f[a[i].first]++;
    }
    for(int i=0;i<m;++i){
        for(int j=a[i].first+a[i].second;j<=n;j+=a[i].second){
            if(!f[j]) continue;
            adj[a[i].first].insert({j,((j-a[i].first)/a[i].second)});
        }
        for(int j=a[i].first-a[i].second;j>=0;j-=a[i].second){
            if(!f[j]) continue;
            adj[a[i].first].insert({j,((a[i].first-j)/a[i].second)});
        }
    }
    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: 0 / 21
• Subtask 5: 0 / 43