제출 #1125318

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125318		Skymagic	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	400 ms	327680 KiB

skyscraper

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include <iostream>
#include <queue>
#define int short
#define tiii pair<short, pair<short, short>>
using namespace std;

short MXN = 30000;
short n, m, dis[30001][175], b, p, d=174, st, en, cnt, cd, cb, cp, nd, nb, np;;
vector<tiii> g[30001][175];
priority_queue<tiii, vector<tiii>, greater<tiii>> pq;

signed main() {
    cin >> n >> m;
    for(int i=0; i<30001; i++) {
        fill(dis[i], dis[i] + 175, 32700);
    }
    for(int i=0; i<m; i++) {
        cin >> b >> p;
        if(i == 0) st = b;
        if(i == 1) en = b;
        if(p*p >= MXN) {
            cnt = 0;
            for(int j=b; j<n; j+=p) {
                g[b][d].push_back({j, {0, cnt}});
                cnt++;
            }
            cnt = 1;
            for(int j=b-p; j>=0; j-=p) {
                g[b][d].push_back({j, {0, cnt}});
                cnt++;
            }
            g[b][0].push_back({b, {d, 0}});
        } else {
            g[b][0].push_back({b, {p, 0}});
        }
    }
    pq.push({0, {st, 0}});
    while(pq.size()) {
        cd = pq.top().first;
        cb = pq.top().second.first;
        cp = pq.top().second.second;
        pq.pop();
        if(cd > dis[cb][cp]) continue;
        for(auto i: g[cb][cp]) {
            nd = cd+i.second.second;
            nb = i.first;
            np = i.second.first;
            if(nd < dis[nb][np]) {
                dis[nb][np] = nd;
                pq.push({nd, {nb, np}});
            }
        }
        if(cp != 0 && cp != d && cb-cp >= 0) {
            if(cd+1 < dis[cb-cp][cp]) {
                dis[cb-cp][cp] = cd+1;
                pq.push({cd+1, {cb-cp, cp}});
            }
        }
        if(cp != 0 && cp != d && cb+cp < n) {
            if(cd+1 < dis[cb+cp][cp]) {
                dis[cb+cp][cp] = cd+1;
                pq.push({cd+1, {cb+cp, cp}});
            }
        }
        if(cp != 0 && cd < dis[cb][0]) {
            dis[cb][0] = cd;
            pq.push({cd, {cb, 0}});
        }
    }
    if(dis[en][0] == 32700) cout << -1;
    else cout << dis[en][0];
    return 0;
}

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