Submission #23446

#	Time	Username	Problem	Language	Result	Execution time	Memory
23446		duongthoi1999	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1000 ms	90020 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
const int mod = (int) 1e9 + 7;
const ll inf = 1LL << 60;
const int maxn = (int) 3e4 + 5;
const ld eps = 1e-9;

int n, m, b[maxn], p[maxn], f[maxn];
unordered_map<int, int> d[maxn];
vector<int> a[maxn];
deque<pair<int, ii> > pq;

int main() {
    //freopen("test.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    rep(i, 0, m) {
        cin >> b[i] >> p[i];
//        b[i] = rand() % n;
//        p[i] = rand() % 30000 + 1;
        a[b[i]].pb(p[i]);
        d[b[i]][p[i]] = mod;
    }
    rep(i, 0, n) {
        sort(all(a[i]));
        a[i].resize(unique(all(a[i])) - a[i].begin());
    }
    d[b[0]][p[0]] = 0;
    pq.push_back(make_pair(0, ii(b[0], p[0])));
    while(!pq.empty()) {
        int du = pq.front().fi;
        int u = pq.front().se.fi;
        int t = pq.front().se.se;
        pq.pop_front();
        if(du != d[u][t]) continue;
        rep(i, -1, 2) if(i) {
            int v = u + i * t;
            if(v < 0 || v >= n) continue;
            if(d[v].count(t) && d[v][t] <= du + 1) continue;
            d[v][t] = du + 1;
            pq.push_back(make_pair(du + 1, ii(v, t)));
        }
        if(f[u]) continue;
        for (auto s : a[u]) {
            d[u][s] = du;
            pq.push_front(make_pair(du, ii(u, s)));
        }
        f[u] = 1;
    }
    if(d[b[1]][p[1]] != mod) cout << d[b[1]][p[1]] << '\n';
    else cout << "-1\n";
}

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