Submission #349923

#	Time	Username	Problem	Language	Result	Execution time	Memory
349923		denkendoemeer	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	341 ms	8672 KiB

skyscraper

#include<bits/stdc++.h>
const int inf=1e9;
using namespace std;
int poz[30005],p[30005],dist[30005];
vector<pair<int,int>>g[30005];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
set<int>st[30005];
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,m,i;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d",&poz[i],&p[i]);
        st[poz[i]].insert(p[i]);
    }
    for(i=0;i<n;i++)
        dist[i]=inf;
    dist[poz[0]]=0;
    pq.push({0,poz[0]});
    while(pq.size()){
        int nod=pq.top().second;
        pq.pop();
        if (nod==poz[1]){
            printf("%d\n",dist[poz[1]]);
            return 0;
        }
        for(auto it:st[nod]){
            for(i=nod+it;i<n;i=i+it){
                if (dist[i]>dist[nod]+(i-nod)/it){
                    dist[i]=dist[nod]+(i-nod)/it;
                    pq.push({dist[i],i});
                }
                if (st[i].count(it))
                    break;
            }
            for(i=nod-it;i>=0;i=i-it){
                if (dist[i]>dist[nod]+(nod-i)/it){
                    dist[i]=dist[nod]+(nod-i)/it;
                    pq.push({dist[i],i});
                }
                if (st[i].count(it))
                    break;
            }
        }
    }
    printf("-1\n");
return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |         scanf("%d%d",&poz[i],&p[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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