Submission #1193762

#TimeUsernameProblemLanguageResultExecution timeMemory
1193762emad234Jakarta Skyscrapers (APIO15_skyscraper)C++20
0 / 100
0 ms324 KiB
#pragma GCC optimize("Ofast,O3,unroll-loops") #pragma GCC target("avx,avx2") #include <bits/stdc++.h> #define ll long long #define F first #define S second #define pii pair<int, int> using namespace std; vector<vector<pii>>v; int pos[2]; vector<int>dist; bool operator<(pair<int,int>a,pair<int,int>b){ return a.S > b.S; } int n,m; int conv(int q,int p){ return p * n + q; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >>n>>m; int buck = 175; dist.resize(n * buck + 1); v.resize(n * buck + 1); for(int i = 0;i < m;i++){ int q,p; cin >>q>>p; if(i < 2) pos[i] = q; if(p <= buck){ v[conv(q,0)].push_back({conv(q,p),0}); }else{ int cnt = 1; for(int j = q - p;j >= 0;j -= p){ v[conv(q,0)].push_back({conv(j,0),cnt}); cnt++; } cnt = 1; for(int j = q + p;j < n;j += p){ v[conv(q,0)].push_back({conv(j,0),cnt}); cnt++; } } } for(int i = 0;i < n;i++){ for(int p = 0;p <= buck;p++){ dist[conv(i,p)] = 1e9; } } dist[pos[0]] = 0; priority_queue<pair<int,int>>q; q.push({pos[0],0}); while(q.size()){ auto u = q.top(); // cout<<u.F<<' '<<u.S<<'\n'; q.pop(); if(dist[u.F] < u.S) continue; for(auto x : v[u.F]){ if(dist[x.F] > u.S + x.S){ dist[x.F] = u.S + x.S; q.push({x.F,dist[x.F]}); } } pii x; if(u.F >= n){ x = {u.F + u.F / n,1}; if(x.F / n == u.F / n && dist[x.F] > u.S + x.S){ dist[x.F] = u.S + x.S; q.push({x.F,dist[x.F]}); } x = {u.F - u.F / n,1}; if(x.F / n == u.F / n && dist[x.F] > u.S + x.S){ dist[x.F] = u.S + x.S; q.push({x.F,dist[x.F]}); } x = {u.F % n,0}; if(dist[x.F] > u.S + x.S){ dist[x.F] = u.S + x.S; q.push({x.F,dist[x.F]}); } } } cout<<(dist[pos[1]] == 1e9 ? -1 : dist[pos[1]]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...