Submission #205422

#	Time	Username	Problem	Language	Result	Execution time	Memory
205422		anonymous	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	92 ms	5612 KiB

skyscraper

#include<iostream>
#include<set>
#include<queue>
#include<utility>
#define MAXN 30005
using namespace std;
int N, M, S, T, bi, pi, dist[MAXN];
bool vis[MAXN];
set <int> D[MAXN];
priority_queue<pair<int,int> > PQ;

int main() {
    //freopen("jarin.txt","r",stdin);
    scanf("%d %d",&N,&M);
    for (int i=0; i<M; i++) {
        scanf("%d %d",&bi,&pi);
        D[bi].insert(pi);
        if (i == 0) {S = bi;}
        else if (i == 1) {T = bi;}
    }
    for (int i=0; i<N; i++) {
        dist[i] = 1<<30;
    }
    dist[S] = 0;
    PQ.push({0, S});
    while (PQ.size()) {
        int cur = PQ.top().second;
        PQ.pop();
        if (vis[cur]) {continue;}
        if (cur == T) {
            printf("%d", dist[cur]);
            return(0);
        }
        vis[cur]=true;
        for (auto p: D[cur]) {
            for (int i=1; i<=N; i++) {
                if (cur + i*p >= N) {break;}
                if (dist[cur + i*p] > dist[cur] + i) {
                    dist[cur + i*p] = dist[cur] + i;
                    PQ.push({-dist[cur + i*p], cur + i*p});
                }
                if (D[cur + i*p].find(p) != D[cur + i*p].end()) {break;}
            }
            for (int i=-1; i>=-N; i--) {
                if (cur + i*p < 0) {break;}
                if (dist[cur + i*p] > dist[cur] - i) {
                    dist[cur + i*p] = dist[cur] - i;
                    PQ.push({-dist[cur + i*p], cur + i*p});
                }
                if (D[cur + i*p].find(p) != D[cur + i*p].end()) {break;}
            }
        }
    }
    printf("-1");
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&M);
     ~~~~~^~~~~~~~~~~~~~~
skyscraper.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&bi,&pi);
         ~~~~~^~~~~~~~~~~~~~~~~

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