제출 #766357

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766357		linkret	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	87 ms	32852 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//const int N = 3e4 + 30, B = 175;
const int N = 2020;
const int inf = 2e9;

vector<int> g[N];
int n, m;
//int dist[N][B];
int dist[N][N];
bool bio[N];

/*
5 3
0 2
1 1
4 1
*/

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

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
        //for(int j = 0; j < B; j++) {
            dist[i][j] = inf;
        }
    }

    cin >> n >> m;

    int s = 0, f = 0;
    for(int i = 0; i < m; i++) {
        int x, k;
        cin >> x >> k;
        g[x].push_back(k);

        if(i == 0) s = x;
        if(i == 1) f = x;
    }

    priority_queue<array<int,3>> pq;

    for(auto x : g[s]) {
//        if(x < B) {
            dist[s][x] = 0;
            pq.push({dist[s][x], s, x});
//        } else {
//            for(int k = 1; s + k * x < N; k++) {
//                dist[s + k * x][0] = k;
//                pq.push({-dist[s + k * x][0], s + k * x, 0});
//            }
//
//            for(int k = 1; s - k * x >= 0; k++) {
//                dist[s - k * x][0] = k;
//                pq.push({-dist[s - k * x][0], s - k * x, 0});
//            }
//        }
    }
    bio[s] = 1;

    while(!pq.empty()) {
        auto top = pq.top();
        int d = get<0>(top);
        int v = get<1>(top);
        int p = get<2>(top);
        pq.pop();
        d = -d;

        if(d > dist[v][p]) continue;

        if(!bio[v]) {
              for(auto x : g[v]) {
//                    if(x < B) {
                          dist[v][x] = d;
                          pq.push({-dist[v][x], v, x});
//                    } else {
//                          for(int k = 1; v + k * x < n; k++) {
//                                if(dist[v + k * x][0] > d + k) {
//                                      dist[v + k * x][0] = d + k;
//                                      pq.push({-dist[v + k * x][0], v + k * x, 0});
//                                }
//                          }
//
//                          for(int k = 1; v - k * x >= 0; k++) {
//                                if(dist[v - k * x][0] > d + k) {
//                                      dist[v - k * x][0] = d + k;
//                                      pq.push({-dist[v - k * x][0], v - k * x, 0});
//                                }
//                          }
//                    }
              }
              bio[v] = 1;
        }

        if(v + p < N && dist[v + p][p] > d + 1) {
              dist[v + p][p] = d + 1;
              pq.push({-dist[v + p][p], v + p, p});
        }

        if(v - p >= 0 && dist[v - p][p] > d + 1) {
              dist[v - p][p] = d + 1;
              pq.push({-dist[v - p][p], v - p, p});
        }
    }

    int ans = inf;
    //for(int k = 0; k < B; k++)
    for(int k = 0; k < N; k++)
        ans = min(ans, dist[f][k]);

    if(ans == inf)
        ans = -1;

    cout << ans << '\n';

    return 0;
}

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