Submission #36801

#	Time	Username	Problem	Language	Result	Execution time	Memory
36801		imaxblue	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	319 ms	20944 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define p_q priority_queue
#define MN 1000000009

int n, m, P, D, X, K, t, p[30005], j[30005], d[30005][105], J;
p_q<pair<int, pii> > pq;
bool u[30005][105];
vector<int> v[30005];
int main(){
    memset(d, 0x3f3f3f3f, sizeof d);
    scanf("%i%i", &n, &m);
    for (int l=0; l<m; ++l){
        scanf("%i%i", &p[l], &j[l]);
        v[p[l]].pb(j[l]);
    }
    X=p[1];
    pq.push(mp(0, mp(p[0], 0))); d[p[0]][0]=0;
    while(!pq.empty()){
        P=pq.top().y.x; K=pq.top().y.y; pq.pop();
        if (u[P][K]) continue;
        u[P][K]=1;
        if (d[P][K]<d[P][0]){
            d[P][0]=d[P][K];
            pq.push(mp(-d[P][K], mp(P, 0)));
        }
        //cout << P << ' ' << d[P] << endl;
        if (P==X){
            cout << d[P][K]; return 0;
        }
        if (K>0){
            if (P-K>=0){
                if (d[P][K]+1<d[P-K][K]){
                    d[P-K][K]=d[P][K]+1; pq.push(mp(-d[P][K]-1, mp(P-K, K)));
                }
            }
            if (P+K<=n){
                if (d[P][K]+1<d[P+K][K]){
                    d[P+K][K]=d[P][K]+1; pq.push(mp(-d[P][K]-1, mp(P+K, K)));
                }
            }
            continue;
        }
        for (int l2=0; l2<v[P].size(); ++l2){
            if (l2>0 && v[P][l2]==v[P][l2-1]) continue;
            J=v[P][l2];
            if (J<50){
                if (P-J>=0){
                    if (d[P][K]+1<d[P-J][J]){
                        d[P-J][J]=d[P][K]+1; pq.push(mp(-d[P][K]-1, mp(P-J, J)));
                    }
                }
                if (P+J<n){
                    if (d[P][K]+1<d[P+J][J]){
                        d[P+J][J]=d[P][K]+1; pq.push(mp(-d[P][K]-1, mp(P+J, J)));
                    }
                }
            }
            else
            for (int l=P%J; l<n; l+=J){
                t=max((l-P)/J, -(l-P)/J)+d[P][K];
                if (t<d[l][0]){
                    d[l][0]=t; pq.push(mp(-t, mp(l, 0)));
                }
            }
        }
        /*for (int l=0; l<m; ++l){
            if ((p[l]-p[P])%j[P]) continue;
            t=max((p[l]-p[P])/j[P], -(p[l]-p[P])/j[P])+d[P];
            if (t<d[l]){
                d[l]=t; pq.push(mp(-t, l));
            }
        }*/
    }
    cout << -1;
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:57:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int l2=0; l2<v[P].size(); ++l2){
                          ^
skyscraper.cpp:25:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i", &n, &m);
                          ^
skyscraper.cpp:27:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i", &p[l], &j[l]);
                                    ^

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