제출 #255956

#제출 시각아이디문제언어결과실행 시간메모리
255956SaacootaJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
1095 ms121328 KiB
#include <bits/stdc++.h> #define fo(i,a,b) for(int i=(a);i<=(b);++i) #define fd(i,a,b) for(int i=(a);i>=(b);--i) #define rep(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se second #define LL unsigned long long #define uint unsigned int #define pb push_back #define eb emplace_back #define bit(s,i) ((s >> i) & 1) #define off(s,i) (s & (~ (1 << i))) #define ii pair <int , int> #define iii1 pair <ii , int> #define iii2 pair <int , ii> #define TASK "SKY" using namespace std; const long long inf = 0x3f3f3f3f3f3f3f3f; const int oo = 0x3f; int n , m , p[30004] , b[30004]; vector < int > vc[30004]; int d[30004][505][2]; struct node { int dis , i , p , type; }; bool operator > (node a , node b) { return a.dis > b.dis; } ///-------------------------- void readf() { cin >> n >> m; } ///-------------------------- void solve() { int sqr = 500; for (int i = 0 ; i < m ; ++i) { cin >> b[i] >> p[i]; vc[b[i]].pb(i); } int ans = 1e9; memset(d,0x3f,sizeof(d)); priority_queue < node , vector < node > , greater < node > > wyna; wyna.push({0 , b[0] , 0 , 0}); d[b[0]][0][0] = 0; while (!wyna.empty()) { node x = wyna.top(); int dis = x.dis , pk = x.p , type = x.type , i = x.i; if (i == b[1]) ans = min(ans , dis); wyna.pop(); if (dis != d[i][pk][type]) continue; if (type == 0) { for (auto x : vc[i]) if (p[x] <= sqr) { if (d[i][p[x]][1] > dis) { d[i][p[x]][1] = dis; wyna.push({dis , i , p[x] , 1}); } } else { int pp = p[x]; int cnt = 0; for (int x = i ; x < n ; x += pp) { if (d[x][0][0] > dis + cnt) { d[x][0][0] = dis + cnt; wyna.push({dis + cnt , x , 0 , 0}); } cnt++; } cnt = 0; for (int x = i ; x >= 0 ; x -= pp) { if (d[x][0][0] > dis + cnt) { d[x][0][0] = dis + cnt; wyna.push({dis + cnt , x , 0 , 0}); } cnt++; } } } if (type == 1) { if (i + pk < n && d[i + pk][pk][1] > dis + 1) { d[i + pk][pk][1] = dis + 1; wyna.push({dis + 1 , i + pk , pk , 1}); } if (i - pk >= 0 && d[i - pk][pk][1] > dis + 1) { d[i - pk][pk][1] = dis + 1; wyna.push({dis + 1 , i - pk , pk , 1}); } if (d[i][0][0] > dis) { d[i][0][0] = dis; wyna.push({dis , i , 0 , 0}); } } } if (ans == 1e9) cout << -1; else cout << ans; } ///-------------------------- int main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); readf(); solve(); }
#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...