Submission #1134874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134874		Roumak77	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	318 ms	327680 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 : 36/100
 *
 * Subtask 4 (21 points)
 * Subtask 5 (43 points)

 */

using ll = int;

void solve(){


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

    vector<vector<pair<ll, ll>>> adj(n, vector<pair<ll, ll>>());
    vector<vector<ll>> list_n(n, vector<ll>());
    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_n[a].push_back(i);
        list_n2[a].push_back(b);
    }

    for(ll i = 0; i < n; i++){
        sort(list_n2[i].rbegin(), list_n2[i].rend());
        vector<bool> vis(n, false);
        for(ll j : list_n2[i]){
            ll temp = i - j;
            while(temp >= 0){
                if(!vis[temp]){
                    adj[i].push_back({temp, (i - temp)/j});
                    vis[temp] = true;
                }

                temp-=j;
            }
            temp = i + j;
            while(temp < n){
                if(!vis[temp]){
                    adj[i].push_back({temp, (temp - i)/j});
                    vis[temp] = true;
                }
                temp+=j;
            }
        }
    }


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

    while(!mult.empty()){
        auto top = *(mult.begin());
        mult.erase(mult.begin());
        if(vis[top.second] < top.first){
            continue;
        }

        for(auto node : adj[top.second]){
            if(vis[node.first] <= top.first + node.second){
                continue;
            }else{
                vis[node.first] = top.first + node.second;
                mult.insert({top.first + node.second, node.first});
            }
        }
    }
    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