제출 #582981

#제출 시각아이디문제언어결과실행 시간메모리
582981Justin1Jakarta Skyscrapers (APIO15_skyscraper)C++14
22 / 100
965 ms262144 KiB
#include <bits/stdc++.h> using namespace std; struct edge{ int v, c; }; const int maxpow = 2000; int n,m,k,x,y,z; int pos[4002005], power[4002005]; vector<edge> gph[4002005]; int dis[4002005], inq[4002005]; deque<int> nxt; int f(int i, int j) { //2d to 1d return (i-1)*maxpow+j; } void spfa() { for (int i = 1; i <= n*maxpow+n; i++) dis[i] = 1e9; dis[f(pos[1],power[1])] = 0; nxt.push_back(f(pos[1],power[1])); inq[f(pos[1],power[1])] = 1; while (nxt.size()) { auto tmp = nxt.front(); nxt.pop_front(); inq[tmp] = 0; for (auto i : gph[tmp]) { if (dis[tmp] + i.c < dis[i.v]) { dis[i.v] = dis[tmp] + i.c; if (!inq[i.v]) nxt.push_back(i.v); inq[i.v] = 1; if (dis[nxt.back()] < dis[nxt.front()]){ nxt.push_front(nxt.back()); nxt.pop_back(); } } } } if (dis[n*maxpow+pos[2]] == 1e9) cout << "-1\n"; else cout << dis[n*maxpow+pos[2]] << '\n'; } int main() { cin.tie(0), cout.tie(0) -> sync_with_stdio(0); cin >> n >> m; for (int i = 1; i <= m; i++) cin >> pos[i] >> power[i]; for (int i = 1; i <= m; i++) pos[i]++; for (int i = 1; i <= maxpow; i++) { //pow for (int j = 1; j <= i; j++) { for (int l = j; l+i <= n; l += i) { //pos gph[f(l,i)].push_back({f(l+i,i),1}); gph[f(l+i,i)].push_back({f(l,i),1}); } } for (int j = 1; j <= n; j++) gph[f(j,i)].push_back({n*maxpow+j,0}); } for (int i = 1; i <= m; i++) gph[n*maxpow+pos[i]].push_back({f(pos[i],power[i]),0}); spfa(); }
#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...