Submission #566184

#	Time	Username	Problem	Language	Result	Execution time	Memory
566184		ac2hu	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	3 ms	852 KiB

skyscraper

#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
#define int long long 
signed main() {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n, m;cin >> n >> m;
    vector<pair<int,int>> doge(m);
    for(auto &[x,y] : doge)cin >> x >> y;
    vector<vector<pair<int,int>>> adj(m);
    for(int i = 0;i<m;i++){
        for(int j = 0;j<m;j++){
            if(i == j)continue;
            assert(doge[i].second != 0);
            int ab = abs(doge[i].first - doge[j].first);
            if(ab%doge[i].second == 0){
               adj[i].push_back({j, ab/doge[i].second}); 
            }
        }
    }
    vector<int> dist(n, 1e18);
    dist[0] = 0;
    priority_queue<pair<int,int>> pq;
    pq.push({-dist[0], 0});
    while(!pq.empty()){
        auto [dd, x] = pq.top();
        pq.pop();
        dd = -dd;
        if(dist[x] < dd)continue;
        for(auto [e, w] : adj[x]){
            if(dist[e] > dist[x] + w){
                dist[e] = dist[x] + w;
                pq.push({-dist[e], e});
            }
        }
    }
    if(dist[1] > 1e17)
        cout << -1 << "\n";
    else
        cout << dist[1] << "\n";
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:14:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for(auto &[x,y] : doge)cin >> x >> y;
      |               ^
skyscraper.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |         auto [dd, x] = pq.top();
      |              ^
skyscraper.cpp:35:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |         for(auto [e, w] : adj[x]){
      |                  ^

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