Submission #98070

#	Time	Username	Problem	Language	Result	Execution time	Memory
98070		Smelskiy	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	244 ms	65508 KiB

skyscraper

#include <bits/stdc++.h>

/*
 unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
 mt19937 g1.seed(seed1);
 
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 */
using namespace std;

const double PI = 2 * acos(0);

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, ll> pill;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<vector<ll>> matrix;

int dp[30001];
set<int> amts[30001];
int src, dest;
int n;

vector<pii> edges[30001];

void solve() {
    priority_queue<pii> q;
    q.push(pii(0, src));
    while(!q.empty()) {
        pii curr = q.top();
        q.pop();
        if(curr.second == dest) {
            printf("%d\n", dp[curr.second]);
            return;
        }
        if(dp[curr.second] != -curr.first) continue;
        for(pii out: edges[curr.second]) {
            int nd = out.first;
            int nw = dp[curr.second] + out.second;
            if(nw < dp[nd]) {
                dp[nd] = nw;
                q.push(pii(-dp[nd], nd));
            }
        }
    }
    printf("-1\n");
}

void loadGraph() {
    for(int i = 0; i < n; i++) {
        for(int out: amts[i]) {
            for(int dx = 1; i - dx * out >= 0; dx++) {
                edges[i].push_back(pii(i-dx*out, dx));
                if(amts[i-dx*out].count(out)) break;
            }
            for(int dx = 1; i + dx * out < n; dx++) {
                edges[i].push_back(pii(i+dx*out, dx));
                if(amts[i+dx*out].count(out)) break;
            }
        }
    }
}

int main() {
    int m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) {
        dp[i] = 1 << 25;
    }
    for(int i = 0; i < m; i++) {
        int loc, jump;
        scanf("%d %d", &loc, &jump);
        amts[loc].insert(jump);
        if(i == 0) {
            src = loc;
            dp[loc] = 0;
        }
        else if(i == 1) {
            dest = loc;
        }
    }
    loadGraph();
    solve();
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:69: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:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &loc, &jump);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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