Submission #622482

#	Time	Username	Problem	Language	Result	Execution time	Memory
622482		socpite	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	888 ms	26948 KiB

skyscraper

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

#define f first
#define s second

typedef long long ll;

const int maxn = 3e4+5;
const int inf = 2e9;

int d[maxn][200], vis[maxn][200];
vector<pair<int, int>> vec[maxn];

priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;

int n, m;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //ifstream cin("input.txt");
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 200; j++)d[i][j]=2e9;
    }
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        vec[a].push_back({b, i});
        if(!i){
            d[a][0]=0;
            pq.push({0, {a, 0}});
        }
    }
    int ans = -1;
    while(!pq.empty()){
        auto x = pq.top().s;
        //cout << x.f << " " << x.s << endl;
        pq.pop();
        if(vis[x.f][x.s])continue;
        if(x.s){
            if(x.f - x.s >= 0 && d[x.f-x.s][x.s] > d[x.f][x.s] +1){
                d[x.f-x.s][x.s] = d[x.f][x.s] +1;
                pq.push({d[x.f-x.s][x.s], {x.f-x.s, x.s}});
            }
            if(x.f + x.s < n && d[x.f+x.s][x.s] > d[x.f][x.s] +1){
                d[x.f+x.s][x.s] = d[x.f][x.s] +1;
                pq.push({d[x.f+x.s][x.s], {x.f+x.s, x.s}});
            }
            if(d[x.f][0] > d[x.f][x.s]){
                d[x.f][0]=d[x.f][x.s];
                pq.push({d[x.f][0], {x.f, 0}});
            }
        }
        else{
            for(auto v: vec[x.f]){
                if(v.s == 1)ans = d[x.f][0];
                if(v.f < 200){
                    if(d[x.f][v.f] > d[x.f][0]){
                        d[x.f][v.f]=d[x.f][0];
                        pq.push({d[x.f][v.f], {x.f, v.f}});
                    }
                }
                else{
                    for(int j = 1; x.f-j*v.f >= 0; j++){
                        int pos = x.f-j*v.f;
                        if(d[pos][0] > d[x.f][x.s]+j){
                            d[pos][0] = d[x.f][x.s]+j;
                            pq.push({d[pos][0], {pos, 0}});
                        }
                    }
                    for(int j = 1; x.f+j*v.f < n; j++){
                        int pos = x.f+j*v.f;
                        if(d[pos][0] > d[x.f][x.s]+j){
                            d[pos][0] = d[x.f][x.s]+j;
                            pq.push({d[pos][0], {pos, 0}});
                        }
                    }
                }
            }
        }
    }
    cout << ans;
}

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