Submission #228942

#	Time	Username	Problem	Language	Result	Execution time	Memory
228942		mehrdad_sohrabi	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1092 ms	24624 KiB

skyscraper

#include <bits/stdc++.h>
typedef int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=3e4+100,sq=173;
ll dis[N][sq];
set <pair <pii,int> > s;
vector <int> a[N];
ll p[N];
void dij(){
    while(s.size()){
        pii v=s.begin()->F;
        ll w=dis[v.F][v.S];
        s.erase(s.begin());
      //  cout << v.F << " " << v.S << " " << w << endl;
        if (v.S==0){
            for (auto e : a[v.F]){
                ll u=p[e];
                //cout << u << endl;
                if (u<sq){
                    if (dis[v.F][u]>w){
                        s.erase({{v.F,u},dis[v.F][u]});
                        dis[v.F][u]=w;
                        s.insert({{v.F,u},dis[v.F][u]});
                    }
                }
                else{
                    for (int i=-v.F/u;i<=N/sq;i++){
                        ll h=v.F+i*u;
                        if (h>=0 && h<N){
                            if (dis[h][0]>w+abs(i)){
                                s.erase({{h,0},dis[h][0]});
                                dis[h][0]=w+abs(i);
                                s.insert({{h,0},dis[h][0]});
                            }
                        }
                    }
                }
            }
            continue;
        }
        ll u=v.S;
        ll h=v.F+u;
        if (h>=0 && h<N && dis[h][0]>w+1){
            s.erase({{h,0},dis[h][0]});
            dis[h][0]=w+1;
            s.insert({{h,0},dis[h][0]});
        }
        if (h>=0 && h<N && dis[h][u]>w+1){
            s.erase({{h,u},dis[h][u]});
            dis[h][u]=w+1;
            s.insert({{h,u},dis[h][u]});
        }
        h=v.F-u;
        if (h>=0 && h<N && dis[h][0]>w+1){
            s.erase({{h,0},dis[h][0]});
            dis[h][0]=w+1;
            s.insert({{h,0},dis[h][0]});
        }
        if (h>=0 && h<N && dis[h][u]>w+1){
            s.erase({{h,u},dis[h][u]});
            dis[h][u]=w+1;
            s.insert({{h,u},dis[h][u]});
        }

    }
}
ll ja[N];
int32_t main(){
    sync;
    ll n,m;
    cin >> n >> m;
    for (int i=0;i<m;i++){
        ll x;
        cin >> x >> p[i];
        a[x].pb(i);
        ja[i]=x;
    }
    for (int i=0;i<N;i++){
        for (int j=0;j<sq;j++){
            dis[i][j]=2e8;
        }
    }
    dis[ja[0]][0]=0;
    s.insert({{ja[0],0},0});
    dij();
    ll x=ja[1];
    if (dis[x][0]>1e8) kill(-1);
    kill(dis[x][0]);
}

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