제출 #847236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847236		vjudge1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	227 ms	15316 KiB

skyscraper

#include <bits/stdc++.h>
#define task ""
#define fi first
#define se second
#define pii pair<int, int>

using namespace std;
using ll = long long;

const ll mod = 998244353;
const int inf = 1e9 + 1;
const int arr = 200001;
const int BLOCK = 100;
struct node{
    int dis, i, p;
};
bool operator > (node a, node b) {
    return a.dis > b.dis;
}
int n, m, p[30004], b[30004];
vector<int> adj[30004];
int d[30004][104];
int res = 1e9;
void solve(){
    memset(d, 0x3f, sizeof d);
    priority_queue<node, vector<node>, greater<node>> pq;
    pq.push({0, b[0], 0});
    d[b[0]][0] = 0;
    while(!pq.empty()){
        node k = pq.top(); pq.pop();
        int dist = k.dis, pk = k.p, i = k.i;
        if(i == b[1])res = min(res, dist);
        if(dist != d[i][pk])continue;
        if(pk == 0){
            for(auto v : adj[i]){
                if(p[v] <= BLOCK){
                    if(d[i][p[v]] > dist){
                        d[i][p[v]] = dist;
                        pq.push({dist, i, p[v]});
                    }
                }
                else{
                    int pp = p[v];
                    int cnt = 0;
                    for (int x = i ; x < n ; x += pp)  { 
                        if (d[x][0] > dist + cnt) {
                            d[x][0] = dist + cnt;
                            pq.push({dist + cnt , x , 0});
                        }
                        cnt++;
                    }
                    cnt = 0;
                    for (int x = i ; x >= 0 ; x -= pp) { 
                        if (d[x][0] > dist + cnt) {
                            d[x][0] = dist + cnt;
                            pq.push({dist + cnt , x , 0});
                        }
                        cnt++;
                    }
                }
            }
        }
        else{
            if (i + pk < n && d[i + pk][pk] > dist + 1) {
                d[i + pk][pk] = dist + 1;
                pq.push({dist + 1 , i + pk , pk});
            }
            if (i - pk >= 0 && d[i - pk][pk] > dist + 1) { 
                d[i - pk][pk] = dist + 1;
                pq.push({dist + 1 , i - pk , pk});
            }
            if (d[i][0] > dist) {
                d[i][0] = dist;
                pq.push({dist , i , 0});
            }
        }
    }
    if(res == 1e9)cout << -1 << '\n';
    else cout << res << '\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    // freopen(task".inp" , "r" , stdin);  
    // freopen(task".out" , "w" , stdout);
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> b[i] >> p[i];
        adj[b[i]].push_back(i);
    }
    solve();
}

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