Submission #1134869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134869		Roumak77	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	1 ms	328 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<pair<ll, ll>> list_m(m, {0, 0});
    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++){
        cin >> list_m[i].first;
        cin >> list_m[i].second;
        if(i == 0){
            zero = list_m[i].first;
        }else if(i == 1){
            one = list_m[i].first;
        }
        list_n[list_m[i].first].push_back(i);
        list_n2[list_m[i].first].push_back(list_m[i].second);
    }

    for(ll i = 0; i < n; i++){

        for(ll j : list_n2[i]){
            ll temp = i - j;
            while(temp >= 0){
                adj[i].push_back({temp, (i - temp)/j});
                temp-=j;
            }
            temp = i + j;
            while(temp < n){
                adj[i].push_back({temp, (temp - i)/j});
                temp+=j;
            }
        }
    }


    multiset<pair<ll, ll>> mult;
    vector<ll> vis(n, 1E17);
    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] == 1E17){
        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();
    }
}

Compilation message (stderr)

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:70:23: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '1.0e+17' to '2147483647' [-Woverflow]
   70 |     vector<ll> vis(n, 1E17);
      |                       ^~~~

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