Submission #393035

#	Time	Username	Problem	Language	Result	Execution time	Memory
393035		giorgikob	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	98 ms	17612 KiB

skyscraper

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 3e4+5, mod = 1e9+7, S = 500;

int n,m;
int sq,pos,power;
int cnt,st,f;
int D[N],fix[N];
vector<pair<int,int>>gr[N];
vector<int>on_pos[N];
bool is[N][S];
int Pos[N];

inline void test_case(){

    cin >> n >> m;
    sq = sqrt(n);
    cnt = n;
    for(int i = 1; i <= m; i++){
        cin >> pos >> power;
        pos++;
        on_pos[pos].pb(power);
        if(power <= sq) is[pos][power] = 1;
        Pos[i] = pos;
    }
    for(int i = 1; i <= cnt; i++) D[i] = 1e9;

    priority_queue<pair<int,int>>q;
    q.push({0,Pos[1]});
    D[Pos[1]] = 0;

    while(q.size()){
        auto p = q.top();
        q.pop();
        int x = p.ss;
        int dist = -p.ff;
        if(fix[x] == 1) continue;
        fix[x] = 1;
        if(x == Pos[2]){
            cout << dist << endl;
            return ;
        }
        sort(on_pos[x].begin(),on_pos[x].end());
        int last = 0;
        for(auto power : on_pos[x]){
            if(power == last) continue;
            last = power;
            for(int to = x+power; to <= n; to += power){
                int new_dist = dist + (to-x)/power;
                if(new_dist < D[to]){
                    D[to] = new_dist;
                    q.push({-D[to],to});
                }
                if(power <= sq && is[to][power]) break;
            }

            for(int to = x-power; to >= 1; to -= power){
                int new_dist = dist + abs(to-x)/power;
                if(new_dist < D[to]){
                    D[to] = new_dist;
                    q.push({-D[to],to});
                }
                if(power <= sq && is[to][power]) break;
            }
        }
    }

    if(D[Pos[2]] == 1e9) D[Pos[2]] = -1;

    cout << D[Pos[2]] << endl;
}

 main(){
    ios::sync_with_stdio(0);

    int T = 1;
    //cin >> T;
    while(T--){
        test_case();
    }
}

Compilation message (stderr)

skyscraper.cpp:78:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   78 |  main(){
      |       ^

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