Submission #37074

#	Time	Username	Problem	Language	Result	Execution time	Memory
37074		leejseo	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	443 ms	8628 KiB

skyscraper

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define all(v) v.begin(), v.end()
#define maxint 2E9

struct Node{
    int u;
    int dist;
    Node (int u_, int d_) {u = u_; dist = d_;}
    bool operator < (const Node &a) const {return dist > a.dist;}
};

int N, M;
int B[30001];
int P[30001];
vector<int> V[30000];
int dist[30000];

void get_input(){
    scanf("%d%d", &N, &M);
    for (int i=0; i<M; i++) {
        scanf("%d%d", &B[i], &P[i]);
        V[B[i]].push_back(P[i]);
    }
    for (int i=0; i<N; i++) {
        sort(all(V[i]));
        V[i].erase(unique(all(V[i])), V[i].end());
    }
}

void dijkstra(){
    for (int i=0; i<N; i++) {
        dist[i] = maxint;
    }
    int start = B[0];
    dist[start] = 0;
    priority_queue<Node> Q;
    Q.push(Node(start, 0));
    while (!Q.empty()){
        int u = Q.top().u;
        int dist_u= Q.top().dist;
        Q.pop();
        if (dist_u > dist[u]){
            continue;
        }
        for (int i=0; i < (V[u]).size(); i++){
            int power = V[u][i];
            int to = u+power;
            int cost = dist_u + 1;
            while (to < N){
                if (dist[to] > cost){
                    dist[to] = cost;
                    Q.push(Node(to, cost));
                    if (binary_search(all(V[to]), power)) break;
                }
                to += power;
                cost += 1;
            }
            to = u-power;
            cost = dist_u + 1;
            while (to >= 0){
                if (dist[to]>cost){
                    dist[to]=cost;
                    Q.push(Node(to, cost));
                    if (binary_search(all(V[to]), power)) break;
                }
                to -= power;
                cost += 1;
            }
        }
    }
}

int main(){
    get_input();
    dijkstra();
    int ans = dist[B[1]];
    if (ans == maxint){
        printf("-1\n");
    }
    else{
        printf("%d\n", ans);
    }
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void dijkstra()':
skyscraper.cpp:50:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i < (V[u]).size(); i++){
                         ^
skyscraper.cpp: In function 'void get_input()':
skyscraper.cpp:24:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
                          ^
skyscraper.cpp:26:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &B[i], &P[i]);
                                    ^

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