Submission #566592

#	Time	Username	Problem	Language	Result	Execution time	Memory
566592		ac2hu	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	789 ms	6612 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;
    n++;
    vector<pair<int,int>> doge(m);
    for(auto &[x,y] : doge)cin >> x >> y;
    vector<vector<int>> val(n);
    for(auto [x, y] : doge){
        val[x].push_back(y);
    }
    vector<int> dist(n, 1e18);
    dist[doge[0].first] = 0;
    priority_queue<pair<int,int>> pq;
    pq.push({-dist[doge[0].first], doge[0].first});
    while(!pq.empty()){
        auto [dd, x] = pq.top();
        pq.pop();
        dd = -dd;
        if(dist[x] < dd)continue;
        for(int e : val[x]){
            int c = 0;
            for(int j = x;j<n;j+=e){
                if(dist[j] > dist[x] + c){
                    dist[j] = dist[x] + c;
                    pq.push({-dist[j], j});
                }
                c++;
            } 
            c = 0;
            for(int j = x;j>=0;j-=e){
                if(dist[j] > dist[x] + c){
                    dist[j] = dist[x] + c;
                    pq.push({-dist[j], j});
                }
                c++;
            } 
        }
    }
    int r = doge[1].first;
    if(dist[r] > 1e17)
        cout << -1 << "\n";
    else
        cout << dist[r] << "\n";
}

Compilation message (stderr)

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

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