Submission #114142

#	Time	Username	Problem	Language	Result	Execution time	Memory
114142		fedoseevtimofey	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1069 ms	33400 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 3e4 + 7;

vector <pair <int, int>> g[N];
int d[N];
const int Inf = 1e9;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n, m;
    cin >> n >> m;
    vector <int> b(m), p(m);
    for (int i = 0; i < m; ++i) {
        cin >> b[i] >> p[i];
    }
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i == j) continue;
            if ((b[i] - b[j]) % p[i] == 0) {
                g[i].emplace_back(j, abs(b[i] - b[j]) / p[i]);
            }
        }
    }
    for (int i = 0; i < m; ++i) d[i] = Inf;
    d[0] = 0;
    set <pair <int, int>> q;
    q.insert({0, 0});
    while (!q.empty()) {
        auto p = *q.begin();
        q.erase(q.begin());
        int u = p.second;
        for (auto &[v, w] : g[u]) {
            if (d[v] > d[u] + w) {
                q.erase({d[v], v});
                d[v] = d[u] + w;
                q.insert({d[v], v});
            }
        }
    }
    cout << (d[1] == Inf ? -1 : d[1]) << '\n';
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:42:20: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         for (auto &[v, w] : g[u]) {
                    ^

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