Submission #338158

#	Time	Username	Problem	Language	Result	Execution time	Memory
338158		bigDuck	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1090 ms	4372 KiB

skyscraper

#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 (stderr)

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 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43