oj.uz

Submission #960684

# Submission time Handle Problem Language Result Execution time Memory
960684 2024-04-10T22:46:20 Z 3omar_ahmed Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 239 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std ;
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()
const int N = 2004 * 2004;
vector < int > dis(N, 1e9);
vector < vector < pair < int , int >>> adj(N);
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

    int n, m;
    cin >> n >> m;
    pair < int , int > first, second;
    vector < vector < int >> arr(1 + n);
    for(int i = 0 ; i < m ; i++) {
        int a, b;
        cin >> a >> b;
        if(i == 0) {
            first = {a, b};
        } else if(i == 1) {
            second = {a, b};
        }
        arr[a].push_back(b);
    }
    for(int i = 0 ; i < n ; i++) {
        for(auto j : arr[i]) {
            int node = (i * (n + 1) + j);
            adj[i * (n + 1) + n + 1].push_back({node, 0});
            adj[node].push_back({i * (n + 1) + n + 1, 0});
            for(int k = 1 ; k <= n ; k++) {
                if(i + j * k < n) {
                    adj[node].push_back({(i + j * k) * (n + 1) + n + 1, k});
                }
                if(i - j * k >= 0) {
                    adj[node].push_back({(i - j * k) * (n + 1) + n + 1, k});
                }
            }
        }
    }
    int st = first.first * (n + 1) + first.second;
    priority_queue < pair < int , int >> pq;
    pq.push({0, st});
    dis[st] = 0; 
    while(pq.size()) {
        auto top = pq.top();
        pq.pop();
        top.first *= -1;
        if(top.first != dis[top.second])
            continue;
        for(auto ch : adj[top.second]) {
            if(dis[ch.first] > top.first + ch.second) {
                dis[ch.first] = top.first + ch.second;
                pq.push({-dis[ch.first], ch.first});
            }
        }
    }
    int ed = second.first * (n + 1) + second.second;
    if(dis[ed] >= 1e8) dis[ed] = -1;
    cout << dis[ed] << endl;
    return 0 ;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 110476 KB Output is correct
2 Correct 26 ms 110492 KB Output is correct
3 Correct 28 ms 110468 KB Output is correct
4 Correct 27 ms 110428 KB Output is correct
5 Correct 27 ms 110428 KB Output is correct
6 Correct 27 ms 110428 KB Output is correct
7 Correct 28 ms 110464 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 110580 KB Output is correct
2 Correct 28 ms 110580 KB Output is correct
3 Correct 26 ms 110424 KB Output is correct
4 Correct 27 ms 110428 KB Output is correct
5 Correct 27 ms 110224 KB Output is correct
6 Correct 26 ms 110428 KB Output is correct
7 Correct 26 ms 110424 KB Output is correct
8 Correct 27 ms 110424 KB Output is correct
9 Correct 26 ms 110332 KB Output is correct
10 Correct 26 ms 110428 KB Output is correct
11 Correct 27 ms 110640 KB Output is correct
12 Correct 44 ms 112592 KB Output is correct
13 Correct 29 ms 112596 KB Output is correct
14 Correct 28 ms 110428 KB Output is correct
15 Correct 27 ms 110520 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 110428 KB Output is correct
2 Correct 26 ms 110256 KB Output is correct
3 Correct 26 ms 110428 KB Output is correct
4 Correct 28 ms 110428 KB Output is correct
5 Correct 28 ms 110428 KB Output is correct
6 Correct 26 ms 110424 KB Output is correct
7 Correct 26 ms 110424 KB Output is correct
8 Correct 26 ms 110428 KB Output is correct
9 Correct 26 ms 110428 KB Output is correct
10 Correct 27 ms 110428 KB Output is correct
11 Correct 27 ms 110428 KB Output is correct
12 Correct 32 ms 112600 KB Output is correct
13 Correct 28 ms 112600 KB Output is correct
14 Correct 27 ms 110428 KB Output is correct
15 Correct 27 ms 110420 KB Output is correct
16 Correct 26 ms 110428 KB Output is correct
17 Correct 29 ms 110684 KB Output is correct
18 Correct 28 ms 110660 KB Output is correct
19 Correct 26 ms 110428 KB Output is correct
20 Correct 89 ms 142676 KB Output is correct
21 Correct 27 ms 110476 KB Output is correct
22 Correct 27 ms 110656 KB Output is correct
23 Correct 28 ms 110700 KB Output is correct
24 Correct 30 ms 110676 KB Output is correct
25 Correct 32 ms 110680 KB Output is correct
26 Correct 80 ms 144560 KB Output is correct
27 Correct 68 ms 144412 KB Output is correct
28 Correct 31 ms 110936 KB Output is correct
29 Correct 29 ms 111192 KB Output is correct
30 Correct 27 ms 110676 KB Output is correct
31 Correct 29 ms 111012 KB Output is correct
32 Correct 29 ms 110724 KB Output is correct
33 Correct 34 ms 111964 KB Output is correct
34 Correct 33 ms 112212 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 110428 KB Output is correct
2 Correct 25 ms 110392 KB Output is correct
3 Correct 26 ms 110428 KB Output is correct
4 Correct 28 ms 110412 KB Output is correct
5 Correct 26 ms 110416 KB Output is correct
6 Correct 26 ms 110500 KB Output is correct
7 Correct 25 ms 110424 KB Output is correct
8 Correct 26 ms 110424 KB Output is correct
9 Correct 26 ms 110276 KB Output is correct
10 Correct 26 ms 110500 KB Output is correct
11 Correct 27 ms 110424 KB Output is correct
12 Correct 30 ms 112600 KB Output is correct
13 Correct 29 ms 112596 KB Output is correct
14 Correct 27 ms 110604 KB Output is correct
15 Correct 29 ms 110548 KB Output is correct
16 Correct 29 ms 110428 KB Output is correct
17 Correct 29 ms 110680 KB Output is correct
18 Correct 27 ms 110612 KB Output is correct
19 Correct 27 ms 110428 KB Output is correct
20 Correct 79 ms 142672 KB Output is correct
21 Correct 26 ms 110560 KB Output is correct
22 Correct 27 ms 110428 KB Output is correct
23 Correct 31 ms 110856 KB Output is correct
24 Correct 30 ms 110676 KB Output is correct
25 Correct 32 ms 110676 KB Output is correct
26 Correct 68 ms 144312 KB Output is correct
27 Correct 67 ms 144308 KB Output is correct
28 Correct 31 ms 110940 KB Output is correct
29 Correct 33 ms 111124 KB Output is correct
30 Correct 29 ms 110744 KB Output is correct
31 Correct 28 ms 110932 KB Output is correct
32 Correct 29 ms 110920 KB Output is correct
33 Correct 33 ms 111952 KB Output is correct
34 Correct 33 ms 112100 KB Output is correct
35 Correct 75 ms 113236 KB Output is correct
36 Correct 33 ms 110940 KB Output is correct
37 Correct 79 ms 114336 KB Output is correct
38 Correct 113 ms 114208 KB Output is correct
39 Correct 104 ms 114512 KB Output is correct
40 Correct 104 ms 114292 KB Output is correct
41 Correct 108 ms 114204 KB Output is correct
42 Runtime error 239 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 110424 KB Output is correct
2 Correct 28 ms 110320 KB Output is correct
3 Correct 31 ms 110492 KB Output is correct
4 Correct 26 ms 110680 KB Output is correct
5 Correct 27 ms 110424 KB Output is correct
6 Correct 26 ms 110424 KB Output is correct
7 Correct 26 ms 110668 KB Output is correct
8 Correct 28 ms 110424 KB Output is correct
9 Correct 27 ms 110428 KB Output is correct
10 Correct 27 ms 110428 KB Output is correct
11 Correct 26 ms 110416 KB Output is correct
12 Correct 30 ms 112488 KB Output is correct
13 Correct 30 ms 112600 KB Output is correct
14 Correct 31 ms 110612 KB Output is correct
15 Correct 31 ms 110452 KB Output is correct
16 Correct 31 ms 110424 KB Output is correct
17 Correct 29 ms 110680 KB Output is correct
18 Correct 27 ms 110672 KB Output is correct
19 Correct 27 ms 110428 KB Output is correct
20 Correct 78 ms 142620 KB Output is correct
21 Correct 30 ms 110440 KB Output is correct
22 Correct 27 ms 110500 KB Output is correct
23 Correct 33 ms 110428 KB Output is correct
24 Correct 33 ms 110828 KB Output is correct
25 Correct 32 ms 110680 KB Output is correct
26 Correct 69 ms 145592 KB Output is correct
27 Correct 68 ms 143800 KB Output is correct
28 Correct 34 ms 110940 KB Output is correct
29 Correct 30 ms 111196 KB Output is correct
30 Correct 28 ms 110696 KB Output is correct
31 Correct 34 ms 110940 KB Output is correct
32 Correct 28 ms 110852 KB Output is correct
33 Correct 33 ms 111952 KB Output is correct
34 Correct 33 ms 111956 KB Output is correct
35 Correct 81 ms 113288 KB Output is correct
36 Correct 35 ms 110932 KB Output is correct
37 Correct 87 ms 114352 KB Output is correct
38 Correct 107 ms 114344 KB Output is correct
39 Correct 103 ms 114516 KB Output is correct
40 Correct 104 ms 114328 KB Output is correct
41 Correct 104 ms 114272 KB Output is correct
42 Runtime error 208 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -