oj.uz

Submission #477407

# Submission time Handle Problem Language Result Execution time Memory
477407 2021-10-02T03:56:03 Z KienTran Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 337 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;

const int O = 3e5 + 5;
const int N = 2e3 + 5;
const int inf = 1e9;

int n, m, b[O], p[O], d[O];
vector <pair <int, int>> g[O];
vector <int> a[O];

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++ i){
        cin >> b[i] >> p[i];
        a[b[i]].push_back(p[i]);
    }

    for (int i = 0; i < n; ++ i){
        for (int j : a[i]){
            for (int z = i % j; z < n; z += j){
                if (z != i){
                    g[i].push_back({z, abs(i - z) / j});
                }
            }
        }
    }

    for (int i = 0; i < n; ++ i) d[i] = inf;

    priority_queue <pair <int, int>> q;
    q.push({0, b[1]}); d[b[1]] = 0;

    while (q.size()){
        int u = q.top().second;
        int du = -q.top().first;

        q.pop();
        if (d[u] != du) continue;

        for (auto i : g[u]){
            int v = i.first;
            int w = i.second;

            if (d[v] > d[u] + w){
                d[v] = d[u] + w;
                q.push({-d[v], v});
            }
        }
    }

    if (d[b[2]] >= 1e9) d[b[2]] = -1;
    cout << d[b[2]];
}

Compilation message

skyscraper.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 7 ms 14412 KB Output is correct
3 Correct 8 ms 14304 KB Output is correct
4 Correct 9 ms 14360 KB Output is correct
5 Correct 8 ms 14348 KB Output is correct
6 Correct 7 ms 14424 KB Output is correct
7 Correct 7 ms 14368 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 7 ms 14412 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 8 ms 14424 KB Output is correct
6 Correct 8 ms 14320 KB Output is correct
7 Correct 8 ms 14412 KB Output is correct
8 Correct 8 ms 14412 KB Output is correct
9 Correct 7 ms 14412 KB Output is correct
10 Correct 8 ms 14412 KB Output is correct
11 Correct 9 ms 14536 KB Output is correct
12 Correct 12 ms 16600 KB Output is correct
13 Correct 11 ms 16712 KB Output is correct
14 Correct 9 ms 14460 KB Output is correct
15 Correct 8 ms 14412 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14388 KB Output is correct
2 Correct 7 ms 14412 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 10 ms 14416 KB Output is correct
5 Correct 7 ms 14428 KB Output is correct
6 Correct 8 ms 14412 KB Output is correct
7 Correct 8 ms 14340 KB Output is correct
8 Correct 7 ms 14412 KB Output is correct
9 Correct 8 ms 14412 KB Output is correct
10 Correct 8 ms 14404 KB Output is correct
11 Correct 8 ms 14540 KB Output is correct
12 Correct 11 ms 16576 KB Output is correct
13 Correct 12 ms 16680 KB Output is correct
14 Correct 8 ms 14412 KB Output is correct
15 Correct 8 ms 14412 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 8 ms 14668 KB Output is correct
18 Correct 8 ms 14412 KB Output is correct
19 Correct 8 ms 14440 KB Output is correct
20 Correct 69 ms 46532 KB Output is correct
21 Correct 9 ms 14412 KB Output is correct
22 Correct 8 ms 14512 KB Output is correct
23 Correct 8 ms 14460 KB Output is correct
24 Correct 9 ms 14540 KB Output is correct
25 Correct 9 ms 14540 KB Output is correct
26 Correct 73 ms 47460 KB Output is correct
27 Correct 67 ms 47432 KB Output is correct
28 Correct 8 ms 14668 KB Output is correct
29 Correct 10 ms 15132 KB Output is correct
30 Correct 9 ms 14668 KB Output is correct
31 Correct 9 ms 14796 KB Output is correct
32 Correct 9 ms 14644 KB Output is correct
33 Correct 11 ms 15692 KB Output is correct
34 Correct 11 ms 15764 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14332 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 8 ms 14304 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 8 ms 14412 KB Output is correct
7 Correct 8 ms 14412 KB Output is correct
8 Correct 8 ms 14340 KB Output is correct
9 Correct 7 ms 14412 KB Output is correct
10 Correct 7 ms 14424 KB Output is correct
11 Correct 8 ms 14540 KB Output is correct
12 Correct 11 ms 16584 KB Output is correct
13 Correct 11 ms 16632 KB Output is correct
14 Correct 8 ms 14504 KB Output is correct
15 Correct 8 ms 14412 KB Output is correct
16 Correct 8 ms 14480 KB Output is correct
17 Correct 9 ms 14644 KB Output is correct
18 Correct 9 ms 14412 KB Output is correct
19 Correct 9 ms 14436 KB Output is correct
20 Correct 69 ms 46496 KB Output is correct
21 Correct 7 ms 14412 KB Output is correct
22 Correct 8 ms 14412 KB Output is correct
23 Correct 9 ms 14540 KB Output is correct
24 Correct 9 ms 14540 KB Output is correct
25 Correct 9 ms 14540 KB Output is correct
26 Correct 70 ms 47476 KB Output is correct
27 Correct 68 ms 47384 KB Output is correct
28 Correct 9 ms 14668 KB Output is correct
29 Correct 10 ms 15052 KB Output is correct
30 Correct 8 ms 14668 KB Output is correct
31 Correct 9 ms 14796 KB Output is correct
32 Correct 8 ms 14684 KB Output is correct
33 Correct 10 ms 15584 KB Output is correct
34 Correct 12 ms 15684 KB Output is correct
35 Correct 16 ms 16332 KB Output is correct
36 Correct 9 ms 14732 KB Output is correct
37 Correct 17 ms 17828 KB Output is correct
38 Correct 21 ms 17388 KB Output is correct
39 Correct 18 ms 17536 KB Output is correct
40 Correct 18 ms 17428 KB Output is correct
41 Correct 20 ms 17228 KB Output is correct
42 Runtime error 330 ms 262148 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 8 ms 14412 KB Output is correct
2 Correct 7 ms 14412 KB Output is correct
3 Correct 7 ms 14376 KB Output is correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 9 ms 14408 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 7 ms 14412 KB Output is correct
8 Correct 8 ms 14412 KB Output is correct
9 Correct 8 ms 14412 KB Output is correct
10 Correct 9 ms 14412 KB Output is correct
11 Correct 9 ms 14468 KB Output is correct
12 Correct 12 ms 16596 KB Output is correct
13 Correct 13 ms 16708 KB Output is correct
14 Correct 9 ms 14472 KB Output is correct
15 Correct 8 ms 14412 KB Output is correct
16 Correct 8 ms 14412 KB Output is correct
17 Correct 9 ms 14668 KB Output is correct
18 Correct 8 ms 14540 KB Output is correct
19 Correct 8 ms 14412 KB Output is correct
20 Correct 76 ms 46600 KB Output is correct
21 Correct 8 ms 14412 KB Output is correct
22 Correct 8 ms 14468 KB Output is correct
23 Correct 8 ms 14412 KB Output is correct
24 Correct 10 ms 14584 KB Output is correct
25 Correct 8 ms 14540 KB Output is correct
26 Correct 72 ms 47436 KB Output is correct
27 Correct 69 ms 47384 KB Output is correct
28 Correct 9 ms 14740 KB Output is correct
29 Correct 10 ms 15052 KB Output is correct
30 Correct 8 ms 14664 KB Output is correct
31 Correct 9 ms 14796 KB Output is correct
32 Correct 9 ms 14668 KB Output is correct
33 Correct 11 ms 15692 KB Output is correct
34 Correct 10 ms 15736 KB Output is correct
35 Correct 16 ms 16332 KB Output is correct
36 Correct 10 ms 14656 KB Output is correct
37 Correct 19 ms 17784 KB Output is correct
38 Correct 19 ms 17272 KB Output is correct
39 Correct 18 ms 17520 KB Output is correct
40 Correct 20 ms 17356 KB Output is correct
41 Correct 20 ms 17216 KB Output is correct
42 Runtime error 337 ms 262148 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -