Submission #111895

#	Time	Username	Problem	Language	Result	Execution time	Memory
111895		mayhoubsaleh	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1064 ms	66196 KiB

skyscraper

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define inf 1e18+100

using namespace std;

const ll N=30300;
priority_queue<pair<ll,ll>>q;
ll n,m;
ll b[N],p[N],dist[N];
vector<ll>a[N];
vector<pair<ll,ll>>v[N];
void fil(ll id){
    for(ll i=0;i<n;i++){
        if(i==id||a[i].empty())continue;
        for(auto j:a[id]){
            if((i%p[j])==(id%p[j])){
                v[id].pb({i,abs(i-id)/p[j]});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(ll i=0;i<m;i++){
        cin>>b[i]>>p[i];
        a[b[i]].pb(i);
    }
    for(ll i=0;i<n;i++){
        if(!a[i].empty())fil(i);
    }

    /*for(ll i=0;i<n;i++){
        if(v[i].empty())continue;
        cout<<i<<": ";
        for(auto j:v[i])cout<<'('<<j.first<<' '<<j.second<<')'<<"      ";cout<<endl;
    }*/

    for(ll i=0;i<n;i++){
        dist[i]=inf;
    }
    q.push({0,b[0]});
    dist[b[0]]=0;
    while(!q.empty()){
        ll u=q.top().second,d=-q.top().first;
        q.pop();
        if(d>dist[u])continue;
        for(auto i:v[u]){
            ll ch=i.first,chd=i.second;
            if(chd+d<dist[ch]){
                dist[ch]=chd+d;
                q.push({-dist[ch],ch});
            }
        }
    }
    if(dist[b[1]]==inf){cout<<-1<<endl;return 0;}
    cout<<dist[b[1]]<<endl;
    return 0;
}

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