oj.uz

답안 #338156

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
338156 2020-12-22T15:16:48 Z bigDuck Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 1 ms 1004 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){
        cout<<d0; break;
    }
    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();




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++){
      |                      ~^~~~~~~~~~~~~~

Subtask #1
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 Incorrect 1 ms 1004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 1 ms 1004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
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 Incorrect 1 ms 1004 KB Output isn't correct
5 Halted 0 ms 0 KB -

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 Incorrect 1 ms 1004 KB Output isn't correct
5 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 Incorrect 1 ms 1004 KB Output isn't correct
5 Halted 0 ms 0 KB -