Submission #370229

#	Time	Username	Problem	Language	Result	Execution time	Memory
370229		BartolM	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	7 ms	4992 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=3e4+5;

int n, m, pos0, pos1;
vector <pii> ls[N];
set <int> S[N];
set <pii> s;
int dist[N];

int dodaj(int a, int b, int c) {
//    printf("%d -> %d == %d\n", a, b, c);
    ls[a].pb(mp(b, c));
//    ls[b].pb(mp(a, c));
}

void dijkstra(int poc) {
    memset(dist, INF, sizeof dist);
    dist[poc]=0;
    s.insert(mp(0, poc));
    while (!s.empty()) {
        pii node=*s.begin();
        s.erase(s.begin());
        for (pii sus:ls[node.Y]) {
            if (sus.Y+node.X>=dist[sus.X]) continue;
            if (s.count(mp(dist[sus.X], sus.X))) s.erase(mp(dist[sus.X], sus.X));
            dist[sus.X]=sus.Y+node.X;
            s.insert(mp(dist[sus.X], sus.X));
        }
    }
}

void solve() {
    for (int i=0; i<n; ++i) {
        for (int x:S[i]) {
            for (int j=i+x; j<n; j+=x) {
                dodaj(i, j, (j-i)/x);
                if (S[j].count(x)) break;
            }
            for (int j=i-x; j>=0; j-=x) {
                dodaj(i, j, (i-j)/x);
                if (S[j].count(x)) break;
            }
        }
    }
    dijkstra(pos0);
    printf("%d\n", dist[pos1]==INF ? -1 : dist[pos1]);
}

void load() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        if (i==0) pos0=a;
        if (i==1) pos1=a;
        S[a].insert(b);
    }
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int dodaj(int, int, int)':
skyscraper.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
   28 | }
      | ^
skyscraper.cpp: In function 'void load()':
skyscraper.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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