제출 #847163

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847163		tuan13	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	4 ms	25948 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int ar = 3e4 + 5;
const int N = 105;
int n, m;
int vt[ar], p[ar];
ll dp[ar][N];
vector<int> adj[ar];

struct tuan {
    ll cost, u, step;
};

bool operator > (tuan a, tuan b) {
    return a.cost > b.cost;
}

void dijktra() {
    for(int i = 0; i < m; ++i) {
        adj[vt[i]].push_back(i);
    }
    priority_queue<tuan, vector<tuan>, greater<tuan>> q;
    memset(dp, 0x3f, sizeof(dp));
    dp[vt[0]][0] = 0;
    q.push({0, vt[0], 0});
    while(q.size()) {
        tuan top = q.top(); q.pop();
        int u = top.u, cost = top.cost, step = top.step;
        if(cost > dp[u][step]) continue;
        if(step == 0) {
            for(int v : adj[u]) {
                if(p[v] >= N) {
                    int bonus = 0;
                    for(int i = u; i < n; i += p[v]) {
                        if(dp[i][0] > cost + bonus) {
                            dp[i][0] = cost + bonus;
                            q.push({dp[i][0], i, 0});
                        }
                        ++bonus;
                    }
                    bonus = 0;
                    for(int i = u; i >= 0; i -= p[v]) {
                        if(dp[i][0] > cost + bonus) {
                            dp[i][0] = cost + bonus;
                            q.push({dp[i][0], i, 0});
                        }
                    }
                    ++bonus;
                }
                else {
                    if(dp[u][p[v]] > cost) {
                        dp[u][p[v]] = cost;
                        q.push({dp[u][p[v]], u, p[v]});
                    }
                }
            }
        }
        else {
            if(u - step >= 0 && dp[u - step][step] > cost + 1) {
                dp[u - step][step] = cost + 1;
                q.push({dp[u - step][step], u - step, step});
            }
            if(u + step < n && dp[u + step][step] > cost + 1) {
                dp[u + step][step] = cost + 1;
                q.push({dp[u + step][step], u + step, step});
            }
            if(dp[u][0] > cost) {
                dp[u][0] = cost;
                q.push({dp[u][0], u, 0});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; ++i) {
        cin >> vt[i] >> p[i];
    }
    dijktra();
    ll ans = 1e18;
    for(int i = 0; i < N; ++i) {
        ans = min(ans, dp[vt[1]][i]);
    }
    if(ans > 1e18) ans = -1;
    cout << ans;
}

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