Submission #469861

#	Time	Username	Problem	Language	Result	Execution time	Memory
469861		amirmohammad_nezami	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	1 ms	1116 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define ll long long
#define PB push_back
#define _sz(e) (int)e.size()
#define pii pair <int , int>
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse,sse4,avx,avx2")

const ll maxn = 3e4 + 4 , N = 2e6 + 4 , mod = 1e9 + 7 , INF = 1e9 + 4 , lg = 43;

int n , m , b[maxn] , p[maxn] , dist[maxn];
vector <pii> edges[maxn];
set <pii> se;

void dijkstra() {
    fill(dist , dist + maxn , INF);
    priority_queue <pii> pq;
    pq.push({dist[0] = 0 , b[0]});

    while(_sz(pq)) {
        pii cur = pq.top();
        pq.pop();
        int v = cur.S;
        for (auto u : edges[v]) {
            if(dist[v] + u.S < dist[u.F]) {
                dist[u.F] = dist[v] + u.S;
                pq.push({-dist[u.F] , u.F});
            }
        }
    }
}

int main() {
    FAST;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> b[i] >> p[i];
        se.insert({b[i] , p[i]});
    }
    for (auto v : se) {
        for (int h = v.F + v.S; h < n; h += v.S) {
            edges[v.F].PB({h , (h - v.F) / v.S});
            if(se.find({h , v.S}) != se.end()) break;
        }
        for (int h = v.F - v.S; h >= 0; h -= v.S) {
            edges[v.F].PB({h , (v.F - h) / v.S});
            if(se.find({h , v.S}) != se.end()) break;
        }
    }
    dijkstra();

    cout << (dist[b[1]] == INF ? -1 : dist[b[1]]) << '\n';
}

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