Submission #105570

#	Time	Username	Problem	Language	Result	Execution time	Memory
105570		Kastanda	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	726 ms	2424 KiB

skyscraper

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 30004;
int n, m, head[N], nxt[N], D[N];
pair < int , int > A[N];
priority_queue < pair < int , int > > Pq;
int main()
{
    memset(nxt, -1, sizeof(nxt));
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
        scanf("%d%d", &A[i].x, &A[i].y), nxt[i] = head[A[i].x], head[A[i].x] = i;
    memset(D, 63, sizeof(D)); D[A[0].x] = 0;
    Pq.push({0, A[0].x});
    while (Pq.size())
    {
        int d = -Pq.top().x, v = Pq.top().y; Pq.pop();
        if (v == A[1].x)
            return !printf("%d\n", d);
        if (d > D[v]) continue;
        for (; ~ head[v]; head[v] = nxt[head[v]])
        {
            int dft = A[head[v]].y;
            d = D[v];
            for (int id = v + dft; id < n; id += dft)
                if (D[id] > (++ d)) D[id] = d, Pq.push({-d, id});
            d = D[v];
            for (int id = v - dft; id >= 0; id -= dft)
                if (D[id] > (++ d)) D[id] = d, Pq.push({-d, id});
        }
    }
    return !printf("-1\n");
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:13: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:15:63: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &A[i].x, &A[i].y), nxt[i] = head[A[i].x], head[A[i].x] = i;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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