oj.uz

답안 #338158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
338158 2020-12-22T15:17:37 Z bigDuck Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 1000 ms 4372 KB 
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int t, n, m, k, b[30010], p[30010];
vector<int> dog[30010];

int d[30010];
bool v[30010];


void dijkstra(){
multiset<pii> ms;
ms.insert({d[1], 1});

while(!ms.empty()){
    auto f=*ms.begin(); ms.erase(ms.begin());
    int d0=f.ft, nod=f.sc;
    if(nod==2){
         return;
    }
    v[nod]=true;
    int b0=b[nod], p0=p[nod];
    int b=b0, p=p0;

    for(int i=b; i>=1; i-=p){
        for(int j=0; j<dog[i].size(); j++){
             int u=dog[i][j];
             int c=(abs(i-b)/p);
            if(!v[u]){
                auto it=ms.find({d[u], u});
                if(it!=ms.end()){
                    ms.erase(it);
                    ms.insert({min(d[u], c+d[nod]), u});
                    d[u]=min(d[u],c+d[nod]);
                }
                else{
                    ms.insert({c+d[nod], u});
                    d[u]=c+d[nod];
                }
            }
        }
    }
        for(int i=b; i<=n; i+=p){
        for(int j=0; j<dog[i].size(); j++){
             int u=dog[i][j];
             int c=(abs(i-b)/p);
            if(!v[u]){
                auto it=ms.find({d[u], u});
                if(it!=ms.end()){
                    ms.erase(it);
                    ms.insert({min(d[u], c+d[nod]), u});
                    d[u]=min(d[u],c+d[nod]);
                }
                else{
                    ms.insert({c+d[nod], u});
                    d[u]=c+d[nod];
                }
            }
        }
    }



}

return;
}




int32_t main(){
INIT
cin>>n>>m;
for(int i=1; i<=m; i++){d[i]=-1;}

for(int i=1; i<=m; i++){
cin>>b[i]>>p[i]; b[i]++;
dog[b[i]].pb(i);
}
d[1]=0;

dijkstra();
cout<<d[2];



return 0;
}

Compilation message

skyscraper.cpp: In function 'void dijkstra()':
skyscraper.cpp:35:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(int j=0; j<dog[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~
skyscraper.cpp:53:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int j=0; j<dog[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~
skyscraper.cpp:26:9: warning: unused variable 'd0' [-Wunused-variable]
   26 |     int d0=f.ft, nod=f.sc;
      |         ^~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 1004 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 1024 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 1004 KB Output is correct
5 Correct 1 ms 1132 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 1004 KB Output is correct
8 Correct 3 ms 1004 KB Output is correct
9 Correct 1 ms 1024 KB Output is correct
10 Correct 1 ms 1132 KB Output is correct
11 Correct 2 ms 1132 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 755 ms 1388 KB Output is correct
14 Correct 24 ms 1260 KB Output is correct
15 Correct 24 ms 1260 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 1004 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1024 KB Output is correct
7 Correct 1 ms 1004 KB Output is correct
8 Correct 2 ms 1004 KB Output is correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 2 ms 1132 KB Output is correct
11 Correct 2 ms 1132 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 764 ms 1324 KB Output is correct
14 Correct 24 ms 1260 KB Output is correct
15 Correct 26 ms 1260 KB Output is correct
16 Correct 1 ms 1132 KB Output is correct
17 Correct 7 ms 1260 KB Output is correct
18 Correct 1 ms 1132 KB Output is correct
19 Correct 1 ms 1132 KB Output is correct
20 Correct 355 ms 1260 KB Output is correct
21 Correct 1 ms 1132 KB Output is correct
22 Correct 1 ms 1132 KB Output is correct
23 Correct 2 ms 1132 KB Output is correct
24 Correct 4 ms 1260 KB Output is correct
25 Correct 2 ms 1260 KB Output is correct
26 Correct 2 ms 1132 KB Output is correct
27 Correct 2 ms 1260 KB Output is correct
28 Correct 2 ms 1132 KB Output is correct
29 Correct 5 ms 1132 KB Output is correct
30 Correct 1 ms 1132 KB Output is correct
31 Correct 2 ms 1132 KB Output is correct
32 Correct 2 ms 1132 KB Output is correct
33 Correct 24 ms 1260 KB Output is correct
34 Correct 24 ms 1260 KB Output is correct

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 1004 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 1004 KB Output is correct
8 Correct 1 ms 1004 KB Output is correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 2 ms 1132 KB Output is correct
11 Correct 2 ms 1132 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 764 ms 1388 KB Output is correct
14 Correct 24 ms 1260 KB Output is correct
15 Correct 24 ms 1260 KB Output is correct
16 Correct 1 ms 1132 KB Output is correct
17 Correct 8 ms 1260 KB Output is correct
18 Correct 1 ms 1164 KB Output is correct
19 Correct 1 ms 1132 KB Output is correct
20 Correct 356 ms 1388 KB Output is correct
21 Correct 1 ms 1132 KB Output is correct
22 Correct 1 ms 1132 KB Output is correct
23 Correct 2 ms 1132 KB Output is correct
24 Correct 4 ms 1260 KB Output is correct
25 Correct 2 ms 1260 KB Output is correct
26 Correct 1 ms 1132 KB Output is correct
27 Correct 2 ms 1260 KB Output is correct
28 Correct 2 ms 1132 KB Output is correct
29 Correct 5 ms 1132 KB Output is correct
30 Correct 1 ms 1132 KB Output is correct
31 Correct 2 ms 1132 KB Output is correct
32 Correct 2 ms 1132 KB Output is correct
33 Correct 24 ms 1260 KB Output is correct
34 Correct 24 ms 1260 KB Output is correct
35 Correct 542 ms 3948 KB Output is correct
36 Correct 4 ms 1388 KB Output is correct
37 Correct 132 ms 3196 KB Output is correct
38 Correct 288 ms 4280 KB Output is correct
39 Correct 8 ms 2540 KB Output is correct
40 Correct 19 ms 3820 KB Output is correct
41 Correct 157 ms 4332 KB Output is correct
42 Correct 6 ms 2284 KB Output is correct
43 Correct 14 ms 4076 KB Output is correct
44 Execution timed out 1087 ms 4116 KB Time limit exceeded
45 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 1004 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 1004 KB Output is correct
8 Correct 1 ms 1004 KB Output is correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 2 ms 1132 KB Output is correct
11 Correct 1 ms 1132 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 758 ms 1388 KB Output is correct
14 Correct 24 ms 1388 KB Output is correct
15 Correct 24 ms 1260 KB Output is correct
16 Correct 1 ms 1132 KB Output is correct
17 Correct 7 ms 1260 KB Output is correct
18 Correct 1 ms 1132 KB Output is correct
19 Correct 1 ms 1132 KB Output is correct
20 Correct 352 ms 1388 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1132 KB Output is correct
23 Correct 2 ms 1132 KB Output is correct
24 Correct 4 ms 1260 KB Output is correct
25 Correct 2 ms 1260 KB Output is correct
26 Correct 1 ms 1132 KB Output is correct
27 Correct 2 ms 1260 KB Output is correct
28 Correct 2 ms 1132 KB Output is correct
29 Correct 5 ms 1132 KB Output is correct
30 Correct 1 ms 1132 KB Output is correct
31 Correct 3 ms 1132 KB Output is correct
32 Correct 2 ms 1132 KB Output is correct
33 Correct 24 ms 1260 KB Output is correct
34 Correct 25 ms 1260 KB Output is correct
35 Correct 542 ms 3820 KB Output is correct
36 Correct 4 ms 1388 KB Output is correct
37 Correct 142 ms 3180 KB Output is correct
38 Correct 287 ms 4332 KB Output is correct
39 Correct 9 ms 2540 KB Output is correct
40 Correct 19 ms 3820 KB Output is correct
41 Correct 156 ms 4332 KB Output is correct
42 Correct 10 ms 2284 KB Output is correct
43 Correct 15 ms 4076 KB Output is correct
44 Execution timed out 1090 ms 4372 KB Time limit exceeded
45 Halted 0 ms 0 KB -