Submission #40092

#	Time	Username	Problem	Language	Result	Execution time	Memory
40092		ztrong	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	1000 ms	237676 KiB

skyscraper

#include <bits/stdc++.h>
#define llint long long
#define fi first
#define se second
#define BIT(x, i) ((x>>i)&1ll)
#define MASK(i) (1ll<<i)
#define db(x) cout << #x << " = " << x << endl;
using namespace std;

void openFile() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
#ifdef Tr___
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    //freopen("tname.inp", "r", stdin);
    //freopen("tname.out", "w", stdout);
#endif
}
template <typename T>
inline void read(T &ret){
	register char c = getchar(); bool neg = false; ret = 0;
	while (c < '0' || c > '9'){ if (c == '-') neg = true; c = getchar(); }
	while (c >= '0' && c <= '9'){ ret = (ret << 1) + (ret << 3) + c - '0'; 
        c = getchar(); }
	if (neg) ret = -ret;
}

template <typename T>
void write(T x){
	if (x < 0){ putchar('-'); x = -x; }
	if (x >= 10) write(x / 10); putchar(x % 10 + 48);
}

const int maxn = 3e4 + 5;
const int maxm = 1e6 + 5;
const llint inf = 1e9 + 7;
const int maxk = 2000;

int N, M;
int b[maxn], p[maxn];
vector<int> vertex[maxn];
int edge[maxn][maxk];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
bool inq[maxn];
int d[maxn];

void enter() {
    read(N); read(M);
    for (int i = 0; i < M; ++i) {
        read(b[i]); read(p[i]);
        //if (p[i] < maxk) {
        //    if (!edge[b[i]][p[i]]) {
        //        edge[b[i]][p[i]] = true;
        //        for (int j = b[i]; j >= 1; j -= p[i]) {
        //            edge[j][p[i]] = true;
        //        }
        //        for (int j = b[i]; j <= N; j += p[i]) {
        //            edge[j][p[i]] = true;
        //        }
        //    }
        //}
        //else {
        vertex[b[i]].push_back(p[i]);
        //}
    }
}

void solve() {
    fill_n(d, maxn, inf);
    d[b[0]] = 0;
    //inq[0] = true;
    q.push(make_pair(0, b[0]));
    while (!q.empty()) {
        int u = q.top().se; 
        if (q.top().fi > d[u]) continue;
        q.pop();
        //inq[u] = false;
        //for (int k = 1; k < maxk; ++k) {
        //    if (edge[u][k]) {
        //        int v = u + k;
        //        if (v < N && d[v] > d[u] + 1) {
        //            d[v] = d[u] + 1;
        //            if (!inq[v]) {
        //                q.push(v);
        //                inq[v] = true;
        //            }
        //        }

        //        v = u - k;
        //        if (v >= 0 && d[v] > d[u] + 1) {
        //            d[v] = d[u] + 1;
        //            if (!inq[v]) {
        //                q.push(v);
        //                inq[v] = true;
        //            }
        //        }
        //    }
        //}

        for (auto k : vertex[u]) {
            for (int j = u; j < N; j += k) {
                if (d[j] > d[u] + (j - u) / k) {
                    d[j] = d[u] + (j - u) / k;
                    q.push(make_pair(d[j], j));
                }
            }
            for (int j = u; j >= 0; j -= k) {
                if (d[j] > d[u] + (u - j) / k) {
                    d[j] = d[u] + (u - j) / k;
                    q.push(make_pair(d[j], j));
                }
            }
        }
    }

    if (d[b[1]] == inf) d[b[1]] = -1;
    cout << d[b[1]] << endl;
}

int main() {
    openFile();
    enter();
    solve();
    return 0;
}

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