oj.uz

답안 #695221

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
695221 2023-02-04T19:46:12 Z Ahmed57 Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 489 ms 262144 KB 
#include <bits/stdc++.h>
//#include "game.h"
using namespace std;
vector<int> ind[2001];
int len[30001];
int n,m;
int nah;
long long d(int b){
    long long cost[m][n];
    for(int i = 0;i<m;i++)for(int j = 0;j<n;j++)cost[i][j] = 1e18;
    priority_queue<pair<long long,pair<int,int>>> q1;
    q1.push({0,{0,b}});
    cost[0][b] = 0;
    while(!q1.empty()){
        long long co = q1.top().first*-1;
        long long dog = q1.top().second.first;
        long long indx = q1.top().second.second;
        q1.pop();
        if(co>cost[dog][indx]) continue ;
        for(auto i:ind[indx]){
            if(cost[i][indx]>(cost[dog][indx])){
                cost[i][indx] = (cost[dog][indx]);
                q1.push({cost[i][indx]*-1,{i,indx}});
            }
        }
        if(indx+len[dog]>=0&&indx+len[dog]<n){
            if(cost[dog][indx+len[dog]]>(cost[dog][indx]+1)){
               cost[dog][indx+len[dog]] = (cost[dog][indx]+1);
               q1.push({cost[dog][indx+len[dog]]*-1,{dog,indx+len[dog]}});
            }
        }
        if(indx-len[dog]>=0&&indx-len[dog]<n){
            if(cost[dog][indx-len[dog]]>(cost[dog][indx]+1)){
               cost[dog][indx-len[dog]] = (cost[dog][indx]+1);
               q1.push({cost[dog][indx-len[dog]]*-1,{dog,indx-len[dog]}});
            }
        }
    }
    return cost[1][nah];
}
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;
        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:54:22: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     long long val = d(z);
      |                     ~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 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 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 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 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 596 KB Output is correct
11 Correct 3 ms 2004 KB Output is correct
12 Correct 28 ms 2084 KB Output is correct
13 Correct 23 ms 2004 KB Output is correct
14 Correct 2 ms 2004 KB Output is correct
15 Correct 2 ms 2004 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 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 0 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 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 596 KB Output is correct
11 Correct 3 ms 2004 KB Output is correct
12 Correct 23 ms 2004 KB Output is correct
13 Correct 24 ms 2004 KB Output is correct
14 Correct 2 ms 2004 KB Output is correct
15 Correct 2 ms 2004 KB Output is correct
16 Correct 2 ms 1620 KB Output is correct
17 Correct 9 ms 10708 KB Output is correct
18 Correct 7 ms 13908 KB Output is correct
19 Correct 5 ms 9044 KB Output is correct
20 Correct 487 ms 31928 KB Output is correct
21 Correct 3 ms 3924 KB Output is correct
22 Correct 6 ms 10324 KB Output is correct
23 Correct 7 ms 12372 KB Output is correct
24 Correct 16 ms 28500 KB Output is correct
25 Correct 17 ms 31656 KB Output is correct
26 Correct 398 ms 31928 KB Output is correct
27 Correct 380 ms 31828 KB Output is correct
28 Correct 17 ms 31708 KB Output is correct
29 Correct 16 ms 11988 KB Output is correct
30 Correct 3 ms 3156 KB Output is correct
31 Correct 8 ms 9556 KB Output is correct
32 Correct 7 ms 7892 KB Output is correct
33 Correct 37 ms 31704 KB Output is correct
34 Correct 36 ms 31700 KB Output is correct

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 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 0 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 596 KB Output is correct
11 Correct 3 ms 2004 KB Output is correct
12 Correct 23 ms 2004 KB Output is correct
13 Correct 24 ms 2004 KB Output is correct
14 Correct 2 ms 2004 KB Output is correct
15 Correct 2 ms 2004 KB Output is correct
16 Correct 1 ms 1620 KB Output is correct
17 Correct 10 ms 10680 KB Output is correct
18 Correct 10 ms 13908 KB Output is correct
19 Correct 6 ms 8980 KB Output is correct
20 Correct 489 ms 31840 KB Output is correct
21 Correct 2 ms 3924 KB Output is correct
22 Correct 6 ms 10324 KB Output is correct
23 Correct 7 ms 12372 KB Output is correct
24 Correct 16 ms 28496 KB Output is correct
25 Correct 19 ms 31668 KB Output is correct
26 Correct 396 ms 31812 KB Output is correct
27 Correct 390 ms 31808 KB Output is correct
28 Correct 21 ms 31752 KB Output is correct
29 Correct 14 ms 11988 KB Output is correct
30 Correct 3 ms 3156 KB Output is correct
31 Correct 8 ms 9556 KB Output is correct
32 Correct 6 ms 8008 KB Output is correct
33 Correct 34 ms 31756 KB Output is correct
34 Correct 35 ms 31700 KB Output is correct
35 Runtime error 103 ms 262144 KB Execution killed with signal 9
36 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 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 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 596 KB Output is correct
11 Correct 3 ms 2004 KB Output is correct
12 Correct 23 ms 2004 KB Output is correct
13 Correct 23 ms 2084 KB Output is correct
14 Correct 2 ms 2004 KB Output is correct
15 Correct 3 ms 2004 KB Output is correct
16 Correct 1 ms 1620 KB Output is correct
17 Correct 8 ms 10708 KB Output is correct
18 Correct 7 ms 13908 KB Output is correct
19 Correct 4 ms 9044 KB Output is correct
20 Correct 468 ms 31928 KB Output is correct
21 Correct 2 ms 3924 KB Output is correct
22 Correct 5 ms 10324 KB Output is correct
23 Correct 7 ms 12460 KB Output is correct
24 Correct 16 ms 28500 KB Output is correct
25 Correct 19 ms 31700 KB Output is correct
26 Correct 401 ms 31804 KB Output is correct
27 Correct 376 ms 31804 KB Output is correct
28 Correct 19 ms 31700 KB Output is correct
29 Correct 13 ms 11988 KB Output is correct
30 Correct 4 ms 3156 KB Output is correct
31 Correct 8 ms 9556 KB Output is correct
32 Correct 6 ms 7892 KB Output is correct
33 Correct 36 ms 31700 KB Output is correct
34 Correct 35 ms 31820 KB Output is correct
35 Runtime error 107 ms 262144 KB Execution killed with signal 9
36 Halted 0 ms 0 KB -