Submission #338164

#	Time	Username	Problem	Language	Result	Execution time	Memory
338164		bigDuck	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1091 ms	5944 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];
set<int> dog[30010];

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


int g[30010];

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

while(!ms.empty()){
    auto f=*ms.begin(); ms.erase(ms.begin());
    int nod=f.sc;

    if(nod==2){
         return;
    }
    dog[g[nod] ].erase(nod);
    v[nod]=true;
    int b0=b[nod], p0=p[nod];
    int b=b0, p=p0;

    for(int i=b; i>=1; i-=p){
        for(auto it=dog[i].begin(); it!=dog[i].end(); it++){
             int u=*it;
             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(auto it=dog[i].begin(); it!=dog[i].end(); it++){
             int u=*it;
             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]].insert(i);
}
d[1]=0;

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



return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43