Submission #1215708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215708		zhenja	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	22 / 100	83 ms	123720 KiB

skyscraper

#include <iostream>
#include<string>
#include<cmath>
#include<map>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<set>
#include<cstdio>
#include<stack>
#include<ctime>
#include<queue>
#include<deque>
#include<bitset>
#include<random>
#include<fstream>
#include<unordered_map>
#include<unordered_set>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using dbl = double;

# define all(x) x.begin(), x.end()
# define rall(x) x.rbegin(), x.rend()

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}
ll bpow(ll a, ll n) {
    return n == 0 ? 1 : n % 2 ? bpow(a, n - 1) * a : bpow(a * a, n / 2);
}
ll bpowm(ll a, ll n, ll m) {
    return n == 0 ? 1 : n % 2 ? bpowm(a, n - 1, m) * a % m : bpowm(a * a % m, n / 2, m);
}
mt19937 mt(time(0));
const int N = 3e4 + 2, SZ = 8e6 + 2, M = 5e6 + 2, inf = 1e9 + 100, mod = 1e9 + 7, mod2 = 998244353, P = 257;
const ll llinf = 1e18 + 1000;
int n, m, pt, dist[SZ];
vector<pair<int, int>> g[N];
map<int, vector<int>> a[N];
vector<int> vert[M];

void solve() {
    cin >> n >> m;
    pt = n;
    int st, ansx, ansb;
    for (int i = 0; i < m; ++i) {
        if (i == 1) {
            cin >> ansx >> ansb;
        } else {
            int x, b;
            cin >> x >> b;
            if (i == 0) st = x;
            a[b][x % b].push_back(x);
        }
    }
    for (int b = 1; b < n; ++b) {
        for (auto x : a[b]) {
            int p = x.first;
            vector<int> pos = x.second;
            int j = 0;
            for (int i = p; i < n; i += b) {
                if (j + 1 < pos.size() && abs(i - pos[j]) > abs(i - pos[j + 1])) ++j;
                int d = abs(i - pos[j]) / b;
                if(d == 0) g[i].push_back({ pt, 0 });
                g[pt].push_back({ i, 0 });
                if (i > p) {
                    g[pt - 1].push_back({ pt, 1 });
                    g[pt].push_back({ pt - 1, 1 });
                }
                ++pt;
            }
        }
    }
    fill(dist, dist + pt, inf);
    dist[st] = 0;
    vert[0].push_back(st);
    for (int d = 0; d < M; ++d) {
        while(!vert[d].empty()) {
            int v = vert[d].back();
            vert[d].pop_back();
            if (dist[v] < d) continue;
            for (auto p : g[v]) {
                int to = p.first, w = p.second;
                if (d + w < dist[to]) {
                    dist[to] = d + w;
                    vert[dist[to]].push_back(to);
                }
            }
        }
    }
    cout << (dist[ansx] == inf ? -1 : dist[ansx]);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //freopen("coloring.in", "r", stdin);
    //freopen("coloring.out", "w", stdout);

    //ld time1 = clock();

    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
        cout << '\n';
        cout.flush();
    }

    //ld time2 = clock();
    //cerr << "\n\nTIME: " << (time2 - time1) / CLOCKS_PER_SEC;
    return 0;
}

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