oj.uz

Submission #695242

# Submission time Handle Problem Language Result Execution time Memory
695242 2023-02-04T20:13:52 Z Ahmed57 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 128 ms 33240 KB 
#include <bits/stdc++.h>
//#include "game.h"
using namespace std;
vector<long long> ind[2001];
long long len[30001];
long long n,m;
long long nah;
long long d(int b){
    long long cost[n+1][n+1];
    for(int i = 0;i<=n;i++)for(int j = 0;j<=n;j++)cost[i][j] = 1e18;
    priority_queue<pair<long long,pair<long long,long long>>> q1;
    q1.push({0,{len[0],b}});
    cost[len[0]][b] = 0;
    while(!q1.empty()){
        long long co = q1.top().first*-1;
        long long lin = q1.top().second.first;
        long long indx = q1.top().second.second;
        //cout<<lin<<" "<<indx<<"\n";
        q1.pop();
        if(co>cost[lin][indx]) continue ;
        for(auto i:ind[indx]){
            if(cost[len[i]][indx]>(cost[lin][indx])){
                cost[len[i]][indx] = (cost[lin][indx]);
                q1.push({cost[len[i]][indx]*-1,{len[i],indx}});
            }
        }
        if(indx+lin>=0&&indx+lin<n){
            if(cost[lin][indx+lin]>(cost[lin][indx]+1)){
               cost[lin][indx+lin] = (cost[lin][indx]+1);
               q1.push({cost[lin][indx+lin]*-1,{lin,indx+lin}});
            }
        }
        if(indx-lin>=0&&indx-lin<n){
            if(cost[lin][indx-lin]>(cost[lin][indx]+1)){
               cost[lin][indx-lin] = (cost[lin][indx]+1);
               q1.push({cost[lin][indx-lin]*-1,{lin,indx-lin}});
            }
        }
    }
    long long ans = 1e18;
    for(int i = 1;i<=n;i++){
        ans = min(ans,cost[i][nah]);
    }
    return ans;
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    long long z;
    for(int i = 0;i<m;i++){
        long long x,b;
        cin>>x>>b;
        b = min(b,n);
        if(i==1)nah = x;
        if(i==0)z = x;
        len[i] = b;
        ind[x].push_back(i);
    }
    //cout<<z<<" "<<nah<<"\n";
    long long val = d(z);
    if(val==1e18)cout<<-1<<"\n";
    else cout<<val<<"\n";
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:60:22: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |     long long val = d(z);
      |                     ~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 6 ms 4820 KB Output is correct
18 Correct 14 ms 24244 KB Output is correct
19 Correct 23 ms 31604 KB Output is correct
20 Correct 22 ms 31800 KB Output is correct
21 Correct 1 ms 1620 KB Output is correct
22 Correct 17 ms 25176 KB Output is correct
23 Correct 15 ms 20440 KB Output is correct
24 Correct 20 ms 28772 KB Output is correct
25 Correct 20 ms 31700 KB Output is correct
26 Correct 19 ms 31768 KB Output is correct
27 Correct 21 ms 31652 KB Output is correct
28 Correct 22 ms 31700 KB Output is correct
29 Correct 24 ms 31780 KB Output is correct
30 Correct 22 ms 31676 KB Output is correct
31 Correct 23 ms 31692 KB Output is correct
32 Correct 24 ms 31724 KB Output is correct
33 Correct 37 ms 31832 KB Output is correct
34 Correct 36 ms 31808 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 5 ms 4820 KB Output is correct
18 Correct 15 ms 24236 KB Output is correct
19 Correct 18 ms 31664 KB Output is correct
20 Correct 22 ms 31760 KB Output is correct
21 Correct 1 ms 1492 KB Output is correct
22 Correct 13 ms 25184 KB Output is correct
23 Correct 12 ms 20448 KB Output is correct
24 Correct 18 ms 28756 KB Output is correct
25 Correct 18 ms 31668 KB Output is correct
26 Correct 21 ms 31752 KB Output is correct
27 Correct 26 ms 31696 KB Output is correct
28 Correct 23 ms 31748 KB Output is correct
29 Correct 27 ms 31752 KB Output is correct
30 Correct 24 ms 31700 KB Output is correct
31 Correct 26 ms 31644 KB Output is correct
32 Correct 21 ms 31636 KB Output is correct
33 Correct 33 ms 31828 KB Output is correct
34 Correct 36 ms 31776 KB Output is correct
35 Correct 43 ms 17536 KB Output is correct
36 Correct 12 ms 9884 KB Output is correct
37 Correct 75 ms 31104 KB Output is correct
38 Correct 86 ms 33100 KB Output is correct
39 Correct 100 ms 33164 KB Output is correct
40 Correct 96 ms 33180 KB Output is correct
41 Correct 89 ms 33192 KB Output is correct
42 Correct 22 ms 32220 KB Output is correct
43 Correct 27 ms 32212 KB Output is correct
44 Correct 22 ms 32276 KB Output is correct
45 Correct 117 ms 33176 KB Output is correct
46 Correct 114 ms 33240 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 6 ms 4820 KB Output is correct
18 Correct 12 ms 24256 KB Output is correct
19 Correct 17 ms 31700 KB Output is correct
20 Correct 17 ms 31676 KB Output is correct
21 Correct 2 ms 1572 KB Output is correct
22 Correct 15 ms 25172 KB Output is correct
23 Correct 12 ms 20428 KB Output is correct
24 Correct 17 ms 28708 KB Output is correct
25 Correct 19 ms 31720 KB Output is correct
26 Correct 20 ms 31720 KB Output is correct
27 Correct 18 ms 31768 KB Output is correct
28 Correct 18 ms 31764 KB Output is correct
29 Correct 22 ms 31736 KB Output is correct
30 Correct 20 ms 31648 KB Output is correct
31 Correct 21 ms 31720 KB Output is correct
32 Correct 24 ms 31688 KB Output is correct
33 Correct 39 ms 31744 KB Output is correct
34 Correct 43 ms 31828 KB Output is correct
35 Correct 52 ms 17576 KB Output is correct
36 Correct 9 ms 9796 KB Output is correct
37 Correct 80 ms 31140 KB Output is correct
38 Correct 92 ms 33172 KB Output is correct
39 Correct 100 ms 33220 KB Output is correct
40 Correct 105 ms 33188 KB Output is correct
41 Correct 102 ms 33164 KB Output is correct
42 Correct 31 ms 32272 KB Output is correct
43 Correct 31 ms 32296 KB Output is correct
44 Correct 23 ms 32252 KB Output is correct
45 Correct 128 ms 33200 KB Output is correct
46 Correct 113 ms 33228 KB Output is correct
47 Runtime error 1 ms 468 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -