Submission #657334

#	Time	Username	Problem	Language	Result	Execution time	Memory
657334		Ronin13	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	697 ms	56496 KiB

skyscraper

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int NMAX = 30001;
bool used[NMAX][151];
bool use1[NMAX][151];
vector <vector <int> > vv(NMAX);
vector <pii> g[NMAX];
int d[NMAX][151];

int main(){
    int n; cin >> n;
    int m; cin >> m;
    int b[m + 1], p[m + 1];
    for(int i = 0; i < m; i++){
        cin >> b[i] >> p[i];
        if(p[i] > 150){
            int x = b[i] - p[i];
            int cnt = 1;
            while(x >= 0){
                g[b[i]].pb({x, cnt++});
                x -= p[i];
            }
            x = b[i] + p[i];
            cnt = 1;
            while(x < n){
                g[b[i]].pb({x, cnt++});
                x += p[i];
            }
            continue;
        }
        if(!use1[b[i]][p[i]])
            use1[b[i]][p[i]] = true, vv[b[i]].pb(p[i]);
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= 150; j++)
            d[i][j] = 1e9;
    }
    d[b[0]][0] = 0;
    priority_queue<pair<int, pii> > q;
    q.push({0, {b[0], 0}});
    while(!q.empty()){
        int x = q.top().s.s, v = q.top().s.f;
        q.pop();
        if(used[v][x]) continue;
        used[v][x] = true;
        if(x == 0){
            for(int to : vv[v]){
                if(d[v][to] > d[v][x])
                    d[v][to] = d[v][x], q.push({-d[v][to], {v, to}});
            }
            for(auto to : g[v]){
                if(d[to.f][0] > d[v][x] + to.s)
                    d[to.f][0] = d[v][x] + to.s, q.push({-d[to.f][0], {to.f,0}});
            }
        }
        else{
            if(d[v][0] > d[v][x])
                d[v][0] = d[v][x], q.push({-d[v][0], {v, 0}});
            if(v >= x && d[v - x][x] > d[v][x] + 1)
                d[v - x][x] = d[v][x] + 1, q.push({-d[v - x][x], {v - x, x}});
            if(v + x < n && d[v + x][x] > d[v][x] + 1)
                d[v + x][x] = d[v][x] + 1, q.push({-d[v + x][x], {v + x, x}});
        }
    }
    if(d[b[1]][0] == 1e9)
        d[b[1]][0] = -1;
    cout << d[b[1]][0];
    return 0;
}

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