Submission #45446

#	Time	Username	Problem	Language	Result	Execution time	Memory
45446		RayaBurong25_1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	339 ms	32636 KiB

skyscraper

#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#define INF 1000000007
int B[30005], P[30005];
int AdjList[2005][2005];
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 < N; i++)
        for (j = 0; j < N; j++)
            AdjList[i][j] = INF;
    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]][j] = std::min(AdjList[B[i]][j], abs(B[i] - j)/P[i]);
        }
    }
    for (i = 0; i < N; i++)
        Min[i] = INF;
    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());
        // printf("pop %d %d\n", p.u, p.w);
        if (p.u == B[1])
        {
            printf("%d", p.w);
            return 0;
        }

        for (i = 0; i < N; i++)
        {
            w = AdjList[p.u][i];
            if (p.w + w < Min[i])
            {
                if (Min[i] != INF)
                    Q.erase({i, Min[i]});
                Min[i] = p.w + w;
                Q.insert({i, Min[i]});
            }
        }
    }
    printf("-1");
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:47:9: warning: unused variable 'v' [-Wunused-variable]
     int v, w, s;
         ^
skyscraper.cpp:47:15: warning: unused variable 's' [-Wunused-variable]
     int v, w, s;
               ^
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: 21 / 21
• Subtask 5: 0 / 43