Submission #45443

#	Time	Username	Problem	Language	Result	Execution time	Memory
45443		RayaBurong25_1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	1088 ms	33460 KiB

skyscraper

#include <stdio.h>
#include <vector>
#include <queue>
#define INF 1000000007
int B[30005], P[30005];
std::vector<std::pair<int, int> > AdjList[30005];
int abs(int a)
{
    return (a < 0)?-a:a;
}
int Min[30005];
typedef struct node node;
struct node
{
    int u, w;
};
bool operator<(node a, node b)
{
    return (a.w > b.w);
}
std::priority_queue<node> Q;
int main()
{
    int N, M;
    scanf("%d %d", &N, &M);
    int i, j;
    for (i = 0; i < M; i++)
        scanf("%d %d", &B[i], &P[i]);
    for (i = 0; i < M; i++)
    {
        for (j = 0; j < M; j++)
        {
            if (i == j) continue;
            if (abs(B[i] - B[j])%P[i] == 0)
                AdjList[i].push_back({j, abs(B[i] - B[j])/P[i]});
        }
        Min[i] = INF;
    }
    Min[0] = 0;
    Q.push({0, 0});
    node p;
    int v, w, s;
    while (!Q.empty())
    {
        do
        {
            p = Q.top();
            Q.pop();
        } while (Min[p.u] < p.w);
        if (p.u == 1)
        {
            printf("%d", p.w);
            return 0;
        }

        s = AdjList[p.u].size();
        for (i = 0; i < s; i++)
        {
            v = AdjList[p.u][i].first;
            w = AdjList[p.u][i].second;
            if (p.w + w < Min[v])
            {
                Min[v] = p.w + w;
                Q.push({v, Min[v]});
            }
        }
    }
    printf("-1");
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:25: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:28:14: 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: 0 / 21
• Subtask 5: 0 / 43