Submission #824070

#	Time	Username	Problem	Language	Result	Execution time	Memory
824070		lprochniak	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	259 ms	231992 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long

const int max_ans = 5000000;
const int maxN = 30005;
const int maxSqrtN = 200;

int n,m;
int zero,one;
int root;
vector<int> powers[maxN];
vector<ll> q[max_ans];
bool done[maxN][maxSqrtN];
ll Encode(int building,int power){
    assert(power <= maxSqrtN);
    return building + n*power;
}
int dijkstra(){
    int curr_ans = 0;
    int best_ans = -1;
    q[0].pb(Encode(zero,0));
    while(curr_ans < max_ans){
        if(q[curr_ans].empty()){
            curr_ans++;
            continue;
        }

        ll top = q[curr_ans].back();
        q[curr_ans].pop_back();

        int building = top%n;
        int power = top/n;

        if(done[building][power]) continue;
        done[building][power] = true;

        if(building == one){
            if(best_ans == -1){
                best_ans = curr_ans;
            }
            continue;
        }

        //in building
        if(!power){
            for(ll doge:powers[building]){
                //doge in building
                if(doge<=root){
                    q[curr_ans].pb(Encode(building,doge));
                } else{
                    //other building (power>root)
                    for(int dir=-1;dir<2;dir+=2){
                        for(int jumps=1;;jumps++){
                            int pos = building + jumps*dir*doge;
                            if(pos<0 || pos>=n) break;
                            q[curr_ans+jumps].pb(Encode(pos,0));
                        }
                    }
                }
            }
        } else{
            //doge with power <= root
            
            //to building
            q[curr_ans].pb(Encode(building,0));

            //to other doge
            int pos = building + power;
            if(pos<n) q[curr_ans+1].pb(Encode(pos,power));
            pos = building - power;
            if(pos>=0) q[curr_ans+1].pb(Encode(pos,power));
        }
    }
    return best_ans;
}
int main(){
    cin>>n>>m;
    root = (int)sqrt(n);
    for(int i=0;i<m;i++){
        int building,power;
        cin>>building>>power;
        powers[building].pb(power);

        if(i==0) zero = building;
        if(i==1) one = building;
    }
    cout<<dijkstra();
    return 0;
}

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