Submission #245293

#	Time	Username	Problem	Language	Result	Execution time	Memory
245293		fivefourthreeone	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	223 ms	68064 KiB

skyscraper

#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int> 
#define ayaya cout<<"debug"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int mxN = 30001;
ttgl arr[mxN];
set<int> st[mxN];
vector<ttgl> adj[mxN];
int dist[mxN];
int n, m;
int main()
{
    //freopen("filename.in", "r", stdin);
    //freopen("filename.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    owo(i, 0, m) {
        cin>>arr[i].first>>arr[i].second;
        st[arr[i].first].insert(arr[i].second);
    }
    owo(i, 0, n) {
        auto it = st[i].begin();
        while(it!=st[i].end()) {
            int pos = i;
            int diff = *it;
            while(pos+diff<n) {
                adj[i].senpai({pos+diff, (pos+diff-i)/diff});
                if(st[pos+diff].count(diff)) break;
                pos+=diff;
            }
            pos = i;
            while(pos-diff>=0) {
                adj[i].senpai({pos-diff, (i-pos+diff)/diff});
                if(st[pos-diff].count(diff))break;
                pos-=diff;
            }
            it++;
        }
    }
    memset(dist, INF, sizeof(dist));
    int start = arr[0].first;
    priority_queue<ttgl, vector<ttgl>, greater<ttgl>> pq;
    pq.push({0, start});
    dist[start] = 0;
    while(!pq.empty()) {
        auto u = pq.top();
        pq.pop();
        if(u.first!=dist[u.second])continue;
        for(auto nxt: adj[u.second]) {
            if(dist[u.second]+nxt.second<dist[nxt.first]) {
                dist[nxt.first] = dist[u.second]+nxt.second;
                pq.push({dist[nxt.first], nxt.first});
            }
        }
    }
    if(dist[arr[1].first]==INF) {
        cout<<"-1\n";
    }else {
        cout<<dist[arr[1].first]<<"\n";
    }
    return 0;
}

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