Submission #487328

#	Time	Username	Problem	Language	Result	Execution time	Memory
487328		leaked	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	1 ms	224 KiB

skyscraper

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

signed main(){
    fast_iati;
    int n,m;
    cin>>n>>m;
    vec<int>b(m),p(m);
    vec<vec<int>>have(n,vec<int>());
    for(int i=0;i<m;i++)
        cin>>b[i]>>p[i],have[b[i]].pb(i);
    priority_queue<pii,vec<pii>,greater<pii>>pq;
    vec<int>dp(n,2e9);
//    vec<priority_queue<pii>>kek(n,0);
    pq.push({b[0],0});
    dp[b[0]]=0;
    while(!pq.empty()){
        int v=pq.top().s;
        int x=pq.top().f;
        pq.pop();
        if(dp[v]!=x) continue;
        for(auto &u : have[v]){
            int j=b[u]-p[u];
            int cnt=1;
            while(j>=0){
                if(umin(dp[j],dp[v]+cnt))
                    pq.push({dp[j],j});
                j-=p[u];cnt++;
            }
            j=b[u]+p[u];cnt=1;
            while(j<n){
                if(umin(dp[j],dp[v]+cnt))
                    pq.push({dp[j],j});
                j+=p[u];cnt++;
            }
        }
    }
    cout<<(dp[b[1]]==2e9?-1:dp[b[1]]);
    return 0;
}
/*
6 1 3
8 1 2 1 5 4

*/

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