Submission #1192249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192249		user192837	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1097 ms	14404 KiB

skyscraper

#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 30005;
const ll inf = 1e18;
vector <int> hv[N];
set <int> g[N];
vector <ar <int, 2>> e[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    int strt = -1, end = -1;
    for (int i = 0; i < m; i++) {
        int b, p;
        cin >> b >> p;
        if (i == 0)
            strt = b;
        else if (i == 1)
            end = b;
        hv[p].emplace_back(b);
        g[b].insert(p);
    }
    for (int i = 0; i < n; i++)
        sort(all(hv[i]));
    vector <int> brk(n);
    for (int x = 0; x < n; x++) {
        for (int p : g[x]) {
            int lw = lower_bound(all(hv[p]), x) - hv[p].begin() - 1;
            int hi = upper_bound(all(hv[p]), x) - hv[p].begin();
            if (lw >= 0)
                brk[hv[p][lw]] = 1;
            if (hi < hv[p].size())
                brk[hv[p][hi]] = 1;
            int y = x, cnt = 0;
            while (y + p < n) {
                y += p, cnt++;
                e[x].push_back({y, cnt});
                if (brk[y])
                    break;
            }
            y = x, cnt = 0;
            while (y - p >= 0) {
                y -= p, cnt++;
                e[x].push_back({y, cnt});
                if (brk[y])
                    break;
            }
            if (lw >= 0)
                brk[hv[p][lw]] = 0;
            if (hi < hv[p].size())
                brk[hv[p][hi]] = 0;
        }
    }
    vector <ll> vis(n, inf);
    vis[strt] = 0;
    priority_queue <ar <ll, 2>> q;
    q.push({0, strt});
    while (!q.empty()) {
        auto now = q.top(); q.pop();
        int x = now[1];
        if (now[0] != vis[x])
            continue;
        for (auto &nw : e[x]) {
            if (vis[nw[0]] > vis[x] + nw[1]) {
                vis[nw[0]] = vis[x] + nw[1];
                q.push({vis[nw[0]], nw[0]});
            }
        }
    }
    if (vis[end] == inf)
        cout << -1;
    else
        cout << vis[end];
}

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