Submission #14384

#	Time	Username	Problem	Language	Result	Execution time	Memory
14384		tncks0121	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	71 ms	2836 KiB

skyscraper

#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <time.h>
#include <limits.h>

using namespace std;

typedef long long ll;
typedef double lf;

const int N_ = 30050;
const int M_ = 30050;

vector<int> jumps[N_];

int N, M;
int target, ans;
int start;

int dst[N_];
bool vis[N_];
void solve1() {
    for(int i = 0; i < N; i++) dst[i] = (int)1e9;
dst[start] = 0;
    for(int rep = 0; rep < N; rep++) {
        int u = -1, d = (int)1e9;
        for(int i = 0; i < N; i++) {
            if(dst[i] < d && !vis[i]) u = i, d = dst[i];
        }
        if(u == -1) {
            ans = -1;
            return;
        }
        if(u == target) {
            ans = d;
            return;
        }
        vis[u] = true;
        for(int e = 0; e < jumps[u].size(); e++) {
            int p = jumps[u][e];
            for(int i = u + p, j = 1; i < N; i += p, j++) {
                if(!vis[i] && dst[i] > dst[u] + j) dst[i] = dst[u] + j;
            }
            for(int i = u - p, j = 1; i >= 0; i -= p, j++) {
                if(!vis[i] && dst[i] > dst[u] + j) dst[i] = dst[u] + j;
            }
        }
    }
}

void solve2() {
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    scanf("%d%d", &N, &M);
    for(int i = 0; i < M; i++) {
        int b, p;
        scanf("%d%d", &b, &p);
        if(i == 0) start = b;
        if(i == 1) target = b;
        if(p < N) jumps[b].push_back(p);
    }

    if(N <= 2000) {
        solve1();
    }else{
        solve2();
    }

    printf("%d\n", ans);
    return 0;
}

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