제출 #243863

#제출 시각아이디문제언어결과실행 시간메모리
243863Leonardo_PaesJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
137 ms262148 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, magic = 2500, inf = 0x3f3f3f3f; int b[maxn], p[maxn], dist1[maxn], dist2[maxn][magic+5]; vector<int> doges[maxn]; bool mark[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(i); } priority_queue<pip, vector<pip>, greater<pip>> fila; memset(dist1, inf, sizeof dist1); memset(dist2, inf, sizeof dist2); fila.push({0, {b[0], 0}}); mark[0] = 1; while(!fila.empty()){ int d = fila.top().f, u = fila.top().s.f, id = fila.top().s.s, power = p[fila.top().s.s]; fila.pop(); if(power <= magic){ if(dist2[u][power] == inf) dist2[u][power] = d; if(u + power < n and dist2[u + power][power] == inf){ fila.push({d + 1, {u + power, id}}); dist2[u + power][power] = d + 1; } if(u - power >= 0 and dist2[u - power][power] == inf){ fila.push({d + 1, {u - power, id}}); dist2[u - power][power] = d + 1; } } else{ if(dist1[u] == inf) dist1[u] = d; if(mark[id]) continue; mark[id] = 1; for(int v=u+power, qtd=1; v<n; v+=power, qtd++) fila.push({d + qtd, {v, id}}); for(int v=u-power, qtd=1; v>=0; v-=power, qtd++) fila.push({d + qtd, {v, id}}); } if(!doges[u].empty()){ for(auto v : doges[u]) fila.push({d, {u, v}}); doges[u].clear(); } } int ans = dist1[b[1]]; for(int i=1; i<=magic; 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...