oj.uz

Submission #469862

# Submission time Handle Problem Language Result Execution time Memory
469862 2021-09-02T07:05:27 Z amirmohammad_nezami Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 2 ms 1228 KB 
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define ll long long
#define PB push_back
#define int long long
#define _sz(e) (int)e.size()
#define pii pair <int , int>
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse,sse4,avx,avx2")

const ll maxn = 3e4 + 4 , N = 2e6 + 4 , mod = 1e9 + 7 , INF = 1e18 + 4 , lg = 43;

int n , m , b[maxn] , p[maxn] , dist[maxn];
vector <pii> edges[maxn];
set <pii> se;

void dijkstra() {
    fill(dist , dist + maxn , INF);
    priority_queue <pii> pq;
    pq.push({dist[0] = 0 , b[0]});

    while(_sz(pq)) {
        pii cur = pq.top();
        pq.pop();
        int v = cur.S;
        for (auto u : edges[v]) {
            if(dist[v] + u.S < dist[u.F]) {
                dist[u.F] = dist[v] + u.S;
                pq.push({-dist[u.F] , u.F});
            }
        }
    }
}

int32_t main() {
    FAST;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> b[i] >> p[i];
        se.insert({b[i] , p[i]});
    }
    for (auto v : se) {
        for (int h = v.F + v.S; h < n; h += v.S) {
            edges[v.F].PB({h , (h - v.F) / v.S});
            if(se.find({h , v.S}) != se.end()) break;
        }
        for (int h = v.F - v.S; h >= 0; h -= v.S) {
            edges[v.F].PB({h , (v.F - h) / v.S});
            if(se.find({h , v.S}) != se.end()) break;
        }
    }
    dijkstra();

    cout << (dist[b[1]] == INF ? -1 : dist[b[1]]) << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 1 ms 1228 KB Output is correct
8 Incorrect 1 ms 1228 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 1228 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 1 ms 1228 KB Output is correct
8 Incorrect 1 ms 1228 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 1 ms 1228 KB Output is correct
8 Incorrect 1 ms 1228 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 1228 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 2 ms 1228 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 1 ms 1228 KB Output is correct
8 Incorrect 1 ms 1228 KB Output isn't correct
9 Halted 0 ms 0 KB -