oj.uz

Submission #1110700

# Submission time Handle Problem Language Result Execution time Memory
1110700 2024-11-10T08:23:13 Z malacia Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 5 ms 1872 KB 
#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,1,n) 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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1616 KB Output is correct
2 Correct 1 ms 1616 KB Output is correct
3 Correct 1 ms 1616 KB Output is correct
4 Correct 2 ms 1784 KB Output is correct
5 Correct 1 ms 1616 KB Output is correct
6 Correct 1 ms 1780 KB Output is correct
7 Correct 2 ms 1616 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1616 KB Output is correct
2 Correct 2 ms 1616 KB Output is correct
3 Correct 2 ms 1616 KB Output is correct
4 Correct 2 ms 1616 KB Output is correct
5 Correct 2 ms 1616 KB Output is correct
6 Correct 1 ms 1616 KB Output is correct
7 Correct 2 ms 1616 KB Output is correct
8 Correct 2 ms 1480 KB Output is correct
9 Correct 2 ms 1616 KB Output is correct
10 Correct 2 ms 1616 KB Output is correct
11 Correct 2 ms 1616 KB Output is correct
12 Correct 2 ms 1616 KB Output is correct
13 Correct 2 ms 1872 KB Output is correct
14 Correct 2 ms 1616 KB Output is correct
15 Correct 2 ms 1616 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1616 KB Output is correct
2 Correct 2 ms 1616 KB Output is correct
3 Correct 2 ms 1616 KB Output is correct
4 Correct 1 ms 1616 KB Output is correct
5 Correct 2 ms 1424 KB Output is correct
6 Correct 2 ms 1784 KB Output is correct
7 Correct 1 ms 1616 KB Output is correct
8 Correct 2 ms 1616 KB Output is correct
9 Correct 2 ms 1616 KB Output is correct
10 Correct 1 ms 1616 KB Output is correct
11 Correct 2 ms 1616 KB Output is correct
12 Correct 2 ms 1672 KB Output is correct
13 Correct 2 ms 1616 KB Output is correct
14 Correct 2 ms 1784 KB Output is correct
15 Correct 2 ms 1784 KB Output is correct
16 Correct 2 ms 1616 KB Output is correct
17 Correct 2 ms 1616 KB Output is correct
18 Correct 2 ms 1552 KB Output is correct
19 Correct 2 ms 1784 KB Output is correct
20 Correct 4 ms 1616 KB Output is correct
21 Correct 2 ms 1616 KB Output is correct
22 Correct 2 ms 1616 KB Output is correct
23 Correct 2 ms 1616 KB Output is correct
24 Correct 2 ms 1616 KB Output is correct
25 Correct 2 ms 1692 KB Output is correct
26 Correct 4 ms 1616 KB Output is correct
27 Correct 4 ms 1616 KB Output is correct
28 Incorrect 2 ms 1616 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1616 KB Output is correct
2 Correct 2 ms 1616 KB Output is correct
3 Correct 1 ms 1616 KB Output is correct
4 Correct 2 ms 1616 KB Output is correct
5 Correct 2 ms 1784 KB Output is correct
6 Correct 2 ms 1616 KB Output is correct
7 Correct 1 ms 1616 KB Output is correct
8 Correct 2 ms 1616 KB Output is correct
9 Correct 2 ms 1616 KB Output is correct
10 Correct 1 ms 1616 KB Output is correct
11 Correct 2 ms 1616 KB Output is correct
12 Correct 2 ms 1616 KB Output is correct
13 Correct 2 ms 1616 KB Output is correct
14 Correct 3 ms 1616 KB Output is correct
15 Correct 2 ms 1616 KB Output is correct
16 Correct 2 ms 1616 KB Output is correct
17 Correct 2 ms 1644 KB Output is correct
18 Correct 2 ms 1616 KB Output is correct
19 Correct 2 ms 1456 KB Output is correct
20 Correct 4 ms 1616 KB Output is correct
21 Correct 2 ms 1672 KB Output is correct
22 Correct 2 ms 1616 KB Output is correct
23 Correct 3 ms 1616 KB Output is correct
24 Correct 2 ms 1616 KB Output is correct
25 Correct 3 ms 1616 KB Output is correct
26 Correct 3 ms 1616 KB Output is correct
27 Correct 4 ms 1628 KB Output is correct
28 Incorrect 2 ms 1616 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1616 KB Output is correct
2 Correct 1 ms 1616 KB Output is correct
3 Correct 2 ms 1616 KB Output is correct
4 Correct 2 ms 1616 KB Output is correct
5 Correct 2 ms 1616 KB Output is correct
6 Correct 1 ms 1616 KB Output is correct
7 Correct 1 ms 1616 KB Output is correct
8 Correct 1 ms 1616 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 2 ms 1616 KB Output is correct
11 Correct 2 ms 1616 KB Output is correct
12 Correct 2 ms 1616 KB Output is correct
13 Correct 2 ms 1616 KB Output is correct
14 Correct 2 ms 1616 KB Output is correct
15 Correct 2 ms 1616 KB Output is correct
16 Correct 2 ms 1784 KB Output is correct
17 Correct 2 ms 1616 KB Output is correct
18 Correct 2 ms 1616 KB Output is correct
19 Correct 2 ms 1784 KB Output is correct
20 Correct 5 ms 1616 KB Output is correct
21 Correct 2 ms 1616 KB Output is correct
22 Correct 2 ms 1616 KB Output is correct
23 Correct 2 ms 1616 KB Output is correct
24 Correct 2 ms 1616 KB Output is correct
25 Correct 2 ms 1616 KB Output is correct
26 Correct 5 ms 1616 KB Output is correct
27 Correct 4 ms 1616 KB Output is correct
28 Incorrect 2 ms 1616 KB Output isn't correct
29 Halted 0 ms 0 KB -