제출 #243351

#제출 시각아이디문제언어결과실행 시간메모리
243351Leonardo_PaesJakarta Skyscrapers (APIO15_skyscraper)C++17
22 / 100
47 ms24056 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; typedef pair<int,pii> pip; #define f first #define s second const int maxn = 3e4+10, root = 180, inf = 0x3f3f3f3f; int b[maxn], p[maxn], dist1[maxn], dist2[maxn][root]; vector<int> doges[maxn]; int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); int n, m; cin >> n >> m; for(int i=0; i<m; i++){ cin >> b[i] >> p[i]; doges[b[i]].push_back(p[i]); } priority_queue<pip, vector<pip>, greater<pip>> fila; memset(dist1, inf, sizeof dist1); memset(dist2, inf, sizeof dist2); fila.push({0, {b[0], p[0]}}); while(!fila.empty()){ int d = fila.top().f, u = fila.top().s.f, power = fila.top().s.s; fila.pop(); if(power <= root){ if(dist2[u][power] != inf) continue; dist2[u][power] = d; if(u + power < n) fila.push({d + 1, {u + power, power}}); if(u - power >= 0) fila.push({d + 1, {u - power, power}}); for(auto x : doges[u]){ if(u + x < n) fila.push({d + 1, {u + x, x}}); if(u - x >= 0) fila.push({d + 1, {u - x, x}}); } } else{ if(dist1[u] != inf) continue; dist1[u] = d; if(u + power < n) fila.push({d + 1, {u + power, power}}); if(u - power >= 0) fila.push({d + 1, {u - power, power}}); for(auto x : doges[u]){ if(u + x < n) fila.push({d + 1, {u + x, x}}); if(u - x >= 0) fila.push({d + 1, {u - x, x}}); } } } int ans = dist1[b[1]]; for(int i=1; i<=root; i++) ans = min(ans, dist2[b[1]][i]); cout << (ans == inf ? -1 : ans) << "\n"; return 0; }
#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...