Submission #105566

#	Time	Username	Problem	Language	Result	Execution time	Memory
105566		Kastanda	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	57 / 100	1064 ms	2416 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;
inline void Add(int v, int i)
{
    nxt[i] = head[v]; head[v] = i;
}
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), Add(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]])
        {
            d = D[v];
            for (int id = v + A[head[v]].y; id < n; id += A[head[v]].y)
                if (D[id] > (++ d)) D[id] = d, Pq.push({-d, id});
            d = D[v];
            for (int id = v - A[head[v]].y; id >= 0; id -= A[head[v]].y)
                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:17: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:19:40: 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), Add(A[i].x, i);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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