Submission #45445

#	Time	Username	Problem	Language	Result	Execution time	Memory
45445		RayaBurong25_1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	643 ms	262144 KiB

skyscraper

#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#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 || (a.w == b.w && a.u < b.u));
}
std::set<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 < N; j++)
        {
            if (B[i] == j) continue;
            if (abs(B[i] - j)%P[i] == 0)
                AdjList[B[i]].push_back({j, abs(B[i] - j)/P[i]});
        }
    }
    for (i = 0; i < N; i++)
    {
        Min[i] = INF;
        std::sort(AdjList[i].begin(), AdjList[i].end());
    }
    Min[B[0]] = 0;
    Q.insert({B[0], 0});
    node p;
    int v, w, s;
    while (!Q.empty())
    {
        p = *Q.begin();
        Q.erase(Q.begin());
        if (p.u == B[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])
            {
                if (Min[v] != INF)
                    Q.erase({v, Min[v]});
                Min[v] = p.w + w;
                Q.insert({v, Min[v]});
            }
        }
    }
    printf("-1");
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:26: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:29: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