oj.uz

Submission #443792

# Submission time Handle Problem Language Result Execution time Memory
443792 2021-07-12T06:21:36 Z impri Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 875 ms 64580 KB 
#include<bits/stdc++.h>
using namespace std;
long long graph[2001][2001];
int main(void){
int n,m;
int arr[30001][2];
cin >> n >> m;
for(int i=0;i<m;i++)
    cin >> arr[i][0] >> arr[i][1];
for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    graph[i][j]=10e13;
for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
        if(abs(arr[i][0]-j)%arr[i][1]==0){
            graph[arr[i][0]][j]=min(graph[arr[i][0]][j],1LL*abs(arr[i][0]-j)/arr[i][1]);
        }
    }
}
long long dist[2001];

for(int i=0;i<n;i++)
    dist[i]=10e14;
dist[arr[0][0]]=0;
priority_queue<pair<long long,int> >q;
q.push({0,arr[0][0]});
while(!q.empty()){
    int cur=q.top().second;
    long long curdist=-q.top().first;
    q.pop();

    for(int i=0;i<n;i++){


         long long nxtdist=graph[cur][i];
         if(curdist+nxtdist<dist[i]){
          dist[i]=curdist+nxtdist;
          q.push({-dist[i],i});

         }
    }
}
if(dist[arr[1][0]]>10e12)cout << -1;
else
cout << dist[arr[1][0]];

}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 972 KB Output is correct
11 Correct 3 ms 984 KB Output is correct
12 Correct 4 ms 972 KB Output is correct
13 Correct 4 ms 972 KB Output is correct
14 Correct 3 ms 972 KB Output is correct
15 Correct 3 ms 972 KB Output is correct
16 Correct 2 ms 1652 KB Output is correct
17 Correct 14 ms 7824 KB Output is correct
18 Correct 27 ms 27932 KB Output is correct
19 Correct 27 ms 31820 KB Output is correct
20 Correct 79 ms 31860 KB Output is correct
21 Correct 5 ms 3276 KB Output is correct
22 Correct 26 ms 28388 KB Output is correct
23 Correct 29 ms 25584 KB Output is correct
24 Correct 53 ms 30404 KB Output is correct
25 Correct 47 ms 31992 KB Output is correct
26 Correct 75 ms 31820 KB Output is correct
27 Correct 72 ms 31852 KB Output is correct
28 Correct 50 ms 31860 KB Output is correct
29 Correct 37 ms 32000 KB Output is correct
30 Correct 27 ms 31948 KB Output is correct
31 Correct 33 ms 31996 KB Output is correct
32 Correct 30 ms 31996 KB Output is correct
33 Correct 51 ms 32048 KB Output is correct
34 Correct 52 ms 31944 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 972 KB Output is correct
11 Correct 3 ms 972 KB Output is correct
12 Correct 4 ms 972 KB Output is correct
13 Correct 4 ms 972 KB Output is correct
14 Correct 3 ms 972 KB Output is correct
15 Correct 3 ms 972 KB Output is correct
16 Correct 2 ms 1612 KB Output is correct
17 Correct 15 ms 7904 KB Output is correct
18 Correct 27 ms 27908 KB Output is correct
19 Correct 27 ms 31836 KB Output is correct
20 Correct 75 ms 31900 KB Output is correct
21 Correct 5 ms 3276 KB Output is correct
22 Correct 27 ms 28492 KB Output is correct
23 Correct 28 ms 25676 KB Output is correct
24 Correct 46 ms 30308 KB Output is correct
25 Correct 51 ms 31968 KB Output is correct
26 Correct 76 ms 31852 KB Output is correct
27 Correct 73 ms 31940 KB Output is correct
28 Correct 48 ms 31852 KB Output is correct
29 Correct 36 ms 32076 KB Output is correct
30 Correct 29 ms 31996 KB Output is correct
31 Correct 33 ms 32000 KB Output is correct
32 Correct 30 ms 31880 KB Output is correct
33 Correct 52 ms 32048 KB Output is correct
34 Correct 51 ms 31976 KB Output is correct
35 Correct 235 ms 22508 KB Output is correct
36 Correct 42 ms 14276 KB Output is correct
37 Correct 252 ms 31168 KB Output is correct
38 Correct 379 ms 32212 KB Output is correct
39 Correct 380 ms 32324 KB Output is correct
40 Correct 371 ms 32236 KB Output is correct
41 Correct 379 ms 32236 KB Output is correct
42 Correct 870 ms 32056 KB Output is correct
43 Correct 842 ms 32188 KB Output is correct
44 Correct 875 ms 32060 KB Output is correct
45 Correct 394 ms 32060 KB Output is correct
46 Correct 386 ms 32064 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 488 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 972 KB Output is correct
11 Correct 3 ms 972 KB Output is correct
12 Correct 4 ms 972 KB Output is correct
13 Correct 4 ms 972 KB Output is correct
14 Correct 3 ms 972 KB Output is correct
15 Correct 3 ms 972 KB Output is correct
16 Correct 2 ms 1612 KB Output is correct
17 Correct 15 ms 7828 KB Output is correct
18 Correct 28 ms 27852 KB Output is correct
19 Correct 27 ms 31872 KB Output is correct
20 Correct 78 ms 31864 KB Output is correct
21 Correct 5 ms 3404 KB Output is correct
22 Correct 25 ms 28440 KB Output is correct
23 Correct 28 ms 25584 KB Output is correct
24 Correct 46 ms 30324 KB Output is correct
25 Correct 48 ms 31888 KB Output is correct
26 Correct 76 ms 31852 KB Output is correct
27 Correct 74 ms 31864 KB Output is correct
28 Correct 47 ms 31820 KB Output is correct
29 Correct 36 ms 32004 KB Output is correct
30 Correct 27 ms 31996 KB Output is correct
31 Correct 32 ms 31940 KB Output is correct
32 Correct 30 ms 31864 KB Output is correct
33 Correct 56 ms 31996 KB Output is correct
34 Correct 52 ms 32012 KB Output is correct
35 Correct 231 ms 22596 KB Output is correct
36 Correct 42 ms 14248 KB Output is correct
37 Correct 252 ms 31168 KB Output is correct
38 Correct 381 ms 32208 KB Output is correct
39 Correct 372 ms 32324 KB Output is correct
40 Correct 374 ms 32240 KB Output is correct
41 Correct 372 ms 32324 KB Output is correct
42 Correct 855 ms 32060 KB Output is correct
43 Correct 839 ms 32068 KB Output is correct
44 Correct 864 ms 32060 KB Output is correct
45 Correct 384 ms 32076 KB Output is correct
46 Correct 384 ms 32076 KB Output is correct
47 Runtime error 70 ms 64580 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -