Submission #1134866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134866		Roumak77	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	0 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;

using ll = long long;

void solve(){


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

    vector<vector<pair<ll, ll>>> adj(n, vector<pair<ll, ll>>());
    vector<pair<ll, ll>> list_n(n, {0, 0});
    for(ll i = 0; i < m; i++){
        cin >> list_n[i].first;
        cin >> list_n[i].second;
    }

    for(ll i = 0; i < m - 1; i++){
        for(ll j = i + 1; j < m; j++){

            if(abs(list_n[j].first - list_n[i].first)%list_n[i].second == 0){
                adj[i].push_back({j, abs(list_n[j].first - list_n[i].first)/list_n[i].second});
            }
            if(abs(list_n[j].first - list_n[i].first)%list_n[j].second == 0){
                adj[j].push_back({i, abs(list_n[j].first - list_n[i].first)/list_n[j].second});
            }


        }
    }


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

    while(!mult.empty()){
        auto top = *(mult.begin());
        mult.erase(mult.begin());

        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[1] == 1E17){
        cout << -1 << endl;
    }else{
        cout << vis[1];
    }

}

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: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43