Submission #1134879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134879		Roumak77	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1094 ms	3008 KiB

skyscraper

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
using namespace std;

/*
 * Score : 57/100
 *
 * Subtask 5 (43 points)

 */

using ll = int;

void solve(){


    ll n, m;
    cin >> n >> m;

    vector<vector<ll>> list_n2(n, vector<ll>());

    ll zero = 0;
    ll one = 0;

    for(ll i = 0; i < m; i++){
        ll a, b;
        cin >> a >> b;

        if(i == 0){
            zero = a;
        }else if(i == 1){
            one = a;
        }
        list_n2[a].push_back(b);
    }




    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> mult;
    vector<ll> vis(n, INT_MAX);
    mult.push({0, zero});
    vis[zero] = 0;

    while(!mult.empty()){
        auto top = mult.top();
        mult.pop();
        if(vis[top.second] < top.first){
            continue;
        }
        ll i = top.second;
        for(ll j : list_n2[i]){
            ll temp = i - j;
            while(temp >= 0){
                if(vis[temp] <= top.first + (i - temp)/j){
                    temp-=j;
                    continue;
                }else{
                    vis[temp] = top.first + (i - temp)/j;
                    mult.push({top.first + (i - temp)/j, temp});
                }
                if(temp == one){
                    break;
                }

                temp-=j;
            }
            temp = i + j;
            while(temp < n){
                if(vis[temp] <= top.first + (temp - i)/j){
                    temp+=j;
                    continue;
                }else{
                    vis[temp] = top.first + (temp - i)/j;
                    mult.push({top.first + (temp - i)/j, temp});
                }
                if(temp == one){
                    break;
                }

                temp+=j;
            }
        }

    }
    if(vis[one] == INT_MAX){
        cout << -1 << endl;
    }else{
        cout << vis[one];
    }

}

bool single = true;

signed main(){

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    ll t = 1;
    if(!single) cin >> t;

    while(t--){
        solve();
    }
}

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