제출 #389755

#제출 시각아이디문제언어결과실행 시간메모리
389755milleniumEeeeJakarta Skyscrapers (APIO15_skyscraper)C++11
57 / 100
1111 ms239156 KiB
#include <bits/stdc++.h> #define fr first #define sc second #define pii pair<int, int> #define pb push_back #define szof(s) (int)s.size() #define all(s) s.begin(), s.end() #define fastInp ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; const int MAXN = 30005; const int SHIFT = 50000; const int S = 130; const int INF = 1e9; int pos[MAXN], p[MAXN]; int n, m; struct node { int v, pw, cost; node () { } node (int v_, int pw_, int cost_) { v = v_; pw = pw_; cost = cost_; } }; struct Compare_node { bool operator () (node const &p1, node const &p2) { if (p1.cost != p2.cost) { return p1.cost < p2.cost; } if (p1.v != p2.v) { return p1.v < p2.v; } return p1.pw < p2.pw; } }; vector <int> big[MAXN]; vector <int> small[MAXN]; vector <node> g[MAXN][S]; int dist[MAXN][S]; bool in(int pos) { return 0 <= pos && pos < n; } signed main() { fastInp; cin >> n >> m; set <int> all_small; for (int i = 0; i < m; i++) { cin >> pos[i] >> p[i]; if (p[i] >= S) { big[pos[i]].pb(p[i]); } else { small[pos[i]].pb(p[i]); all_small.insert(p[i]); } } // node -> v pw cost int cnt = 0; for (int i = 0; i < n; i++) { for (int val : all_small) { if (in(i - val)) { g[i][val].pb(node(i - val, val, 1)); cnt++; } if (in(i + val)) { g[i][val].pb(node(i + val, val, 1)); cnt++; } } sort(all(small[i])); small[i].erase(unique(all(small[i])), small[i].end()); for (int val : small[i]) { g[i][0].pb(node(i, val, 0)); cnt++; } } set <node, Compare_node> pq; vector <bool> used(MAXN, false); memset(dist, -1, sizeof(dist)); pq.insert(node(pos[0], 0, 0)); dist[pos[0]][0] = 0; auto ers = [&](int v, int pw) { auto it = pq.lower_bound(node(v, pw, -INF)); if (it != pq.end() && it->v == v && it->pw == pw) { pq.erase(it); } }; while (!pq.empty()) { int v = pq.begin()->v; int pw = pq.begin()->pw; int cost = pq.begin()->cost; pq.erase(pq.begin()); if (cost > dist[v][pw]) { continue; } if (!used[v]) { // впервые добрались до v used[v] = 1; for (int el : big[v]) { for (int to = v % el; to < n; to += el) { int c = abs(v - to) / el; if (dist[to][0] == -1 || dist[to][0] > cost + c) { dist[to][0] = cost + c; ers(to, 0); pq.insert(node(to, 0, dist[to][0])); } } } } // change our pw if (dist[v][0] == -1 || dist[v][0] > dist[v][pw]) { dist[v][0] = dist[v][pw]; ers(v, 0); pq.insert(node(v, 0, dist[v][pw])); } for (auto el : g[v][pw]) { int new_v = el.v; int new_pw = el.pw; int c = el.cost; if (dist[new_v][new_pw] == -1 || dist[new_v][new_pw] > dist[v][pw] + c) { dist[new_v][new_pw] = dist[v][pw] + c; ers(new_v, new_pw); pq.insert(node(new_v, new_pw, dist[new_v][new_pw])); } } } cout << dist[pos[1]][0] << endl; }
#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...