Submission #1110701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110701		malacia	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	603 ms	5324 KiB

skyscraper

#include<bits/stdc++.h>
#define fo(i,x,n) for(int i=x;i<=n;++i)
#define fi(i,x,n) for(int i=x;i>=n;--i)
#define SYNCHRONIZE ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pil pair<int,ll>
#define BIT(i,mask) ((mask >> (i-1)) & 1)
#define pli pair<ll,int>
#define maxn 50005
#define pll pair<ll,ll>
#define uni(vt) vt.resize(unique(vt.begin(),vt.end()) - vt.begin());
#define DAOBIT(i,mask) ((mask ^ (1ll<<i-1)))
#define OFFBIT(i,mask) ((mask & ~(1ll << (i - 1))))
#define ONBIT(i,mask) ((mask  (1ll << (i - 1))))
const int oo =1e9+7;
using namespace std;
//----------------- STRUCTURE ---------------
struct node {
      int pos , power, dp;
};

struct cmp {
      bool operator() (node &A ,node &B) {
            return A.dp > B.dp;
      }
};
//----------------- DECLARE ------------------
int n, m ,dp[maxn] , hs, bf[maxn];
pii dogs[maxn];
vector<int> vt[maxn];
priority_queue<pii,vector<pii>,greater<pii> > pq;
//----------------- FUNCTION -----------------

//----------------- MAIN PRO ------------------
int main()
{
    SYNCHRONIZE;

    cin >>n >>m;

    fo(i,0,m-1) {
          cin >> dogs[i].first >> dogs[i].second ;
          vt[dogs[i].first].push_back(dogs[i].second);
    }

    fo(i,0,n-1) dp[i] = oo;
    dp[dogs[0].first] = 0;
    pq.push({0,dogs[0].first});

    while(pq.size() > 0) {
       auto [num,u] = pq.top();
       pq.pop();

       if(dp[u] != num) continue;

       for(auto power : vt[u]) {
            for(int v = 1 ; u+v*power < n ; v++) if(dp[u+v*power] > dp[u]+v) {
                  dp[u+v*power] = dp[u] + v;
                  pq.push({dp[u]+v,u+v*power});
            }

            for(int v = 1 ; u-v*power >= 0; ++v) if(dp[u-v*power] > dp[u] + v) {
                  pq.push({dp[u]+v,u-v*power});
                  dp[u-v*power] = dp[u] + v;
            }
       }
    }

    cout << (dp[dogs[1].first] == oo ? -1 : dp[dogs[1].first]) ;

}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:53:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |        auto [num,u] = pq.top();
      |             ^

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