Submission #823613

#	Time	Username	Problem	Language	Result	Execution time	Memory
823613		Dec0Dedd	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	172 ms	74552 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int N = 3e4+10;
const int S = 100;
const int INF = 1e9;

int n, m, d[N+10];

vector<pii> G[N+10];
map<pii, vector<int>> mp;

void dijk(int v, int end) {
    for (int i=0; i<n; ++i) d[i]=INF;
    d[v]=0;

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, v});

    while (!pq.empty()) {
        pii x=pq.top(); pq.pop();
        int v=x.second;
        
        if (x.first > d[v]) continue;
        for (auto u : G[v]) {
            if (d[u.second] > u.first+d[v]) {
                d[u.second]=u.first+d[v];
                pq.push({d[u.second], u.second});
            }
        }   
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>m;
    int end=-1, st=-1;
    for (int i=0; i<m; ++i) {
        int b, p; cin>>b>>p;

        mp[{p, b%p}].push_back(b);
        if (i == 1) end=b;
        if (i == 0) st=b;
    }

    if (end == st) {
        cout<<0<<"\n";
        return 0;
    }

    for (auto [x, v] : mp) {
        int j=x.first;
        if (v.empty()) continue;

        v.push_back(0), v.push_back(n);
        sort(v.begin(), v.end());

        int sz=v.size();
        for (int k=1; k+1<sz; ++k) {
            int i=v[k]-j, ds=1;
            while (i >= v[k-1]) G[v[k]].push_back({ds++, i}), i-=j;
            i=v[k]+j, ds=1;
            while (i <= v[k+1]) G[v[k]].push_back({ds++, i}), i+=j;
        }
    } dijk(st, end);

    if (d[end] == INF) cout<<-1<<"\n";
    else cout<<d[end]<<"\n";   
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:57:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for (auto [x, v] : mp) {
      |               ^

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