Submission #1262699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262699		torment	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	36 / 100	1095 ms	219792 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
const long long inf = 1e18;
set<pair<int, int>> G[N];
long long dist[N], M[N][N];
struct T{
    int node;
    long long dist;
    bool operator<(const T& other)const{
        return dist < other.dist;
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            M[i][j] = inf;
        }
        M[i][i] = 0;
    }
    vector<array<int, 2>>v(m);
    for(int i = 0;i < m;++i){
        int b, p;
        cin >> b >> p;
        v[i] = {b, p};
        for(int j = b;j < n;j += p){
            int w = (j - b) / p;
            if(M[b][j] > w){
                if(M[b][j] != inf){
                    G[b].erase({j, M[b][j]});
                }
                G[b].insert({j, w});
                M[b][j] = w;
            }
        }
        for(int j = b;j >= 0;j -= p){
            int w = (b - j) / p;
            if(M[b][j] > w){
                if(M[b][j] != inf){
                    G[b].erase({j, M[b][j]});
                }
                G[b].insert({j, w});
                M[b][j] = w;
            }
        }
    }
    for(int i = 0;i < n;++i){
        dist[i] = inf;
    }
    int s = v[0][0], t = v[1][0];
    dist[s] = 0;
    priority_queue<T>pq;
    T temp = {s, dist[s]};
    pq.push(temp);
    while(!pq.empty()){
        int node = pq.top().node;
        long long D = pq.top().dist;
        pq.pop();
        if(D != dist[node])continue;
        for(auto t : G[node]){
            int v = t.first, w = t.second;
            if(dist[v] > dist[node] + w){
                dist[v] = dist[node] + w;
                pq.push({v, dist[v]});
            }
        }
    }
    if(dist[t] == inf)dist[t] = -1;
    cout << dist[t] << '\n';
}

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