Submission #39821

#TimeUsernameProblemLanguageResultExecution timeMemory
39821nickyrioJakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
869 ms54100 KiB
#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b ; --i) #define REP(i, a) for (int i = 0, _a = (a); i < _a; ++i) #define pp pair<int, int> #define bit(S, i) (((S) >> i) & 1) #define next __next #define prev __prev #define N 30030 #define sqrtN 200 #define taskname "" using namespace std; int n, m, b[N], p[N]; struct data { int u, jump; long long d; }; struct cmp{ bool operator() (const data &a, const data &b) { return a.d > b.d; } }; priority_queue<data, vector<data>, cmp> heap; long long d[N][sqrtN]; vector<int> smallJump[N], largeJump[N];//, smallJumpVer[N]; void Dijkstra(int start, int finish) { REP(i, n) REP(j, (int)sqrt(n) + 1) d[i][j] = 1e18; d[start][0] = 0; heap.push(data({start, 0, 0})); while (!heap.empty()) { data u = heap.top(); heap.pop(); if (u.u == finish) { cout << u.d; return; } if (d[u.u][u.jump] != u.d) continue; if (u.jump == 0) { // Change value of jump for (int jump : smallJump[u.u]) { if (d[u.u][jump] > d[u.u][0]) { d[u.u][jump] = d[u.u][0]; heap.push(data({u.u, jump, d[u.u][0]})); } } // Large jump ( <= sqrt(n) times because jump > sqrt(n) ) for (int jump : largeJump[u.u]) { int newU = u.u - jump, c = 0; while (newU >= 0) { ++c; if (d[newU][0] > d[u.u][0] + c) { d[newU][0] = d[u.u][0] + c; heap.push(data({newU, 0, d[newU][0]})); } newU -= jump; } newU = u.u + jump, c = 0; while (newU < n) { ++c; if (d[newU][0] > d[u.u][0] + c) { d[newU][0] = d[u.u][0] + c; heap.push(data({newU, 0, d[newU][0]})); } newU += jump; } } } else { // Jump left - right int newU = u.u - u.jump; if (newU >= 0 && d[newU][u.jump] > d[u.u][u.jump] + 1) { d[newU][u.jump] = d[u.u][u.jump] + 1; heap.push(data({newU, u.jump, d[newU][u.jump]})); } newU = u.u + u.jump; if (newU < n && d[newU][u.jump] > d[u.u][u.jump] + 1) { d[newU][u.jump] = d[u.u][u.jump] + 1; heap.push(data({newU, u.jump, d[newU][u.jump]})); } // Change Jump to 0 if (d[u.u][0] > d[u.u][u.jump]) { d[u.u][0] = d[u.u][u.jump]; heap.push(data({u.u, 0, d[u.u][0]})); } } } cout << -1; } int main() { ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cin >> n >> m; int finish, start; FOR(i, 1, m) { int p, b; cin >> b >> p; if (i == 1) start = b; if (i == 2) finish = b; if (p <= (int) sqrt(n)) smallJump[b].push_back(p); else largeJump[b].push_back(p); } Dijkstra(start, finish); }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:109:28: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
     Dijkstra(start, finish);
                            ^
skyscraper.cpp:109:28: warning: 'finish' may be used uninitialized in this function [-Wmaybe-uninitialized]
#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...