oj.uz

Submission #39820

# Submission time Handle Problem Language Result Execution time Memory
39820 2018-01-19T14:18:38 Z nickyrio Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 2 ms 50760 KB 
#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 finish) {
    REP(i, n) REP(j, (int)sqrt(n) + 1) d[i][j] = 1e18;
    d[0][0] = 0;
    heap.push(data({0, 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;
    FOR(i, 1, m) {
        int p, b;
        cin >> b >> p;
        if (i == 2) finish = b;
        if (p <= (int) sqrt(n)) smallJump[b].push_back(p);
        else largeJump[b].push_back(p);
    }
    Dijkstra(finish);
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:108:21: warning: 'finish' may be used uninitialized in this function [-Wmaybe-uninitialized]
     Dijkstra(finish);
                     ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 50760 KB Output is correct
2 Correct 1 ms 50760 KB Output is correct
3 Correct 1 ms 50760 KB Output is correct
4 Correct 1 ms 50760 KB Output is correct
5 Correct 1 ms 50760 KB Output is correct
6 Correct 1 ms 50760 KB Output is correct
7 Correct 1 ms 50760 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 50760 KB Output is correct
2 Correct 1 ms 50760 KB Output is correct
3 Correct 1 ms 50760 KB Output is correct
4 Correct 1 ms 50760 KB Output is correct
5 Correct 1 ms 50760 KB Output is correct
6 Correct 0 ms 50760 KB Output is correct
7 Correct 0 ms 50760 KB Output is correct
8 Incorrect 1 ms 50760 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 50760 KB Output is correct
2 Correct 0 ms 50760 KB Output is correct
3 Correct 1 ms 50760 KB Output is correct
4 Correct 0 ms 50760 KB Output is correct
5 Correct 1 ms 50760 KB Output is correct
6 Correct 1 ms 50760 KB Output is correct
7 Correct 0 ms 50760 KB Output is correct
8 Incorrect 0 ms 50760 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 50760 KB Output is correct
2 Correct 1 ms 50760 KB Output is correct
3 Correct 1 ms 50760 KB Output is correct
4 Correct 0 ms 50760 KB Output is correct
5 Correct 1 ms 50760 KB Output is correct
6 Correct 2 ms 50760 KB Output is correct
7 Correct 2 ms 50760 KB Output is correct
8 Incorrect 1 ms 50760 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 50760 KB Output is correct
2 Correct 1 ms 50760 KB Output is correct
3 Correct 2 ms 50760 KB Output is correct
4 Correct 1 ms 50760 KB Output is correct
5 Correct 1 ms 50760 KB Output is correct
6 Correct 1 ms 50760 KB Output is correct
7 Correct 0 ms 50760 KB Output is correct
8 Incorrect 0 ms 50760 KB Output isn't correct
9 Halted 0 ms 0 KB -