oj.uz

답안 #705168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
705168 2023-03-03T13:21:10 Z bebra Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 2 ms 1832 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define dbg(x) cerr << #x << ": " << x << endl;
 
 
const int MAX_N = 30000 + 5;
const ll INF = 1e9;
set<int> jumps[MAX_N];

ll dist[MAX_N];
bool used[MAX_N];
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, m;
    cin >> n >> m;
    int s, t;


    for (int i = 0; i < m; ++i) {
        int v, k;
        cin >> v >> k;
        if (i == 0) s = v;
        if (i == 1) t = v;
        // for a jump let's save every vertex that includes it
        jumps[v].insert(k);
    }

    for (int v = 0; v < n; ++v) {
        set<int> erased;
        for (auto k : jumps[v]) {
            if (erased.find(k) != erased.end()) continue;
            for (int d = k * 2; d < n; d += k) {
                erased.insert(d);
            }
        }
        for (auto k : erased) {
            jumps[v].erase(k);
        }
    }

    fill_n(dist, n, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.emplace(0, s);
    while (!pq.empty()) {
        auto [curr_dist, v] = pq.top();
        pq.pop();
        if (used[v]) continue;

        used[v] = true;
        dist[v] = curr_dist;

        if (v == t) break;
        if (dist[v] == INF) break;
        
        for (auto k : jumps[v]) {
            for (int u = v + k; u < n; u += k) {
                int w = (u - v) / k;
                if (used[u] || dist[v] + w >= dist[u]) continue;
                dist[u] = dist[v] + w;
                pq.emplace(dist[u], u);
            }
            for (int u = v - k; u >= 0; u -= k) {
                int w = (v - u) / k;
                if (used[u] || dist[v] + w >= dist[u]) continue;
                dist[u] = dist[v] + w;
                pq.emplace(dist[u], u);
            }
        }
    }
 
    if (!used[t]) {
        cout << "-1\n";
    } else {
        cout << dist[t] << '\n';
    }
 
    return 0;
}
 
 
/*
5 3
0 2
1 1
4 1
*/

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:58:9: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |         if (v == t) break;
      |         ^~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1748 KB Output is correct
11 Correct 2 ms 1832 KB Output is correct
12 Correct 1 ms 1712 KB Output is correct
13 Correct 2 ms 1748 KB Output is correct
14 Correct 2 ms 1748 KB Output is correct
15 Incorrect 2 ms 1748 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1748 KB Output is correct
11 Correct 2 ms 1748 KB Output is correct
12 Correct 1 ms 1748 KB Output is correct
13 Correct 2 ms 1748 KB Output is correct
14 Correct 2 ms 1760 KB Output is correct
15 Incorrect 2 ms 1748 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1748 KB Output is correct
11 Correct 2 ms 1748 KB Output is correct
12 Correct 1 ms 1748 KB Output is correct
13 Correct 2 ms 1748 KB Output is correct
14 Correct 2 ms 1748 KB Output is correct
15 Incorrect 2 ms 1748 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1748 KB Output is correct
11 Correct 2 ms 1748 KB Output is correct
12 Correct 1 ms 1620 KB Output is correct
13 Correct 2 ms 1748 KB Output is correct
14 Correct 2 ms 1748 KB Output is correct
15 Incorrect 2 ms 1748 KB Output isn't correct
16 Halted 0 ms 0 KB -