Submission #1110659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110659		trandangquang	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	348 ms	26828 KiB

skyscraper

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

const int N = 3e4+5;
const int inf = 1e9;

struct node {
    int dist, pos, jump;
    bool operator < (const node &o) const {
        return dist > o.dist;
    }
};

int n, m, b[N], p[N], d[N][200];
vector <int> pos[N];

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

    cin >> n >> m;
    int sqrtn = sqrt(n);
    for(int i = 0; i < m; ++i) {
        cin >> b[i] >> p[i];
        pos[b[i]].emplace_back(p[i]);
    }

    int ans = inf;
    priority_queue <node> pq;
    memset(d, 0x3f, sizeof(d));
    d[b[0]][0] = 0;
    pq.push({0, b[0], 0});

    while(pq.size()) {
        node x = pq.top(); pq.pop();
        if(x.pos == b[1]) ans = min(ans, x.dist);
        if(x.dist > d[x.pos][x.jump]) continue;

        if(x.jump == 0) {
            for(int i:pos[x.pos]) {
                if(i <= sqrtn) {
                    if(x.dist < d[x.pos][i]) {  
                        d[x.pos][i] = x.dist;
                        pq.push({x.dist, x.pos, i});
                    }
                }
                else {
                    for(int j = 0; x.pos + j*i < n; ++j) {
                        if(x.pos + j*i >= n) break;
                        if(x.dist + j < d[x.pos + i*j][0]) {
                            d[x.pos + i*j][0] = x.dist + j;
                            pq.push({x.dist+j, x.pos+i*j, 0});
                        }
                    }

                    for(int j = 0; x.pos - i*j >= 0; ++j) {
                        if(x.pos - i*j < 0) break;
                        if(x.dist + j < d[x.pos - i*j][0]) {
                            d[x.pos-i*j][0] = x.dist + j;
                            pq.push({x.dist+j, x.pos-i*j, 0});
                        }
                    }
                }
            }
        }
        else {
            if(x.jump + x.pos < n and d[x.jump+x.pos][x.jump] > x.dist+1) {
                d[x.jump+x.pos][x.jump] = x.dist+1;
                pq.push({x.dist+1, x.jump+x.pos, x.jump});
            }
            
            if(x.pos-x.jump >= 0 and d[x.pos-x.jump][x.jump] > x.dist+1) {
                d[x.pos-x.jump][x.jump] = x.dist+1;
                pq.push({x.dist+1, x.pos-x.jump, x.jump});
            }

            if(x.dist < d[x.pos][0]) {
                d[x.pos][0] = x.dist;
                pq.push({x.dist, x.pos, 0});
            }
        }
    }

    if(ans == inf) cout << -1;
    else cout << ans;
}

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