Submission #739447

#	Time	Username	Problem	Language	Result	Execution time	Memory
739447		Mauve	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1083 ms	241652 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define ss second
#define ff first
#define INF 2000000000000000
#define pb push_back
#define edge pair<ll, pair<ll,ll> > // une, number ,power
#define cost first
#define num second.first
#define pwr second.second
ll n,m,l,r,i,j,ii,jj,k,x,y,D[30001][179],s,e;
vector< edge > v[30001][177]; // number , power (powergu oroi bol power = 179)
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>l>>r;
        if(i==1) s=l;
        if(i==2) e=l;
        if(r>175)
            for(j=1 ; l+r*j<n || l-r*j>=0 ; j++){
                edge a;
                a.num=l+r*j;
                a.pwr=176;
                a.cost=j;
                if(a.num<n) v[l][176].pb(a);
                a.num=l-r*j;
                if(a.num>=0) v[l][176].pb(a);
            }
        else{
            v[l][176].pb({0,{l,r}});
        }
    }
    set<edge> q;
    memset(D,-1,sizeof(D));
    q.insert({0,{s,176}});
    while(!q.empty()){
        ll une, nmbr, power;
        edge foo=*(q.begin());
        une=foo.cost;
        nmbr=foo.num;
        power=foo.pwr;
        q.erase(foo);
        if(D[nmbr][power]!=-1);
        else{
        D[nmbr][power]=une;
        for(edge no : v[nmbr][power]) if(D[no.num][no.pwr]==-1) q.insert({une+no.cost,{no.num,no.pwr}});
        if(power!=176){
            if(D[nmbr][176]==-1) q.insert({une,{nmbr,176}});
            if(nmbr+power<n && D[nmbr+power][power]==-1) q.insert({une+1,{nmbr+power,power}});
            if(nmbr-power>=0 && D[nmbr-power][power]==-1) q.insert({une+1,{nmbr-power,power}});
        }
        }
    }
    cout<<D[e][176];
}

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