oj.uz

Submission #477319

# Submission time Handle Problem Language Result Execution time Memory
477319 2021-10-01T15:51:39 Z KienTran Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 1000 ms 161816 KB 
#include <bits/stdc++.h>

using namespace std;

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

int n, m, Max, b[O], d[O], p[O], dd[O], c[N][N];
vector <int> g[N][N];

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];
        Max = max(Max, p[i]);

        int x = p[i];
        int y = b[i] % p[i];

        dd[i] = c[x][y];
        //c[x][y] = true;
    }

    dd[2] = false;
    for (int i = 1; i <= m; ++ i){
        if (dd[i] == 0){
            for (int j = 1; j <= Max; ++ j) g[j][b[i] % j].push_back(i);
        }
    }

    //for (int i : g[2][0]) cout << "have " << i << endl;

    for (int i = 1; i <= m; ++ i) d[i] = inf;

    d[1] = 0;
    priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q;
    q.push(make_pair(0, 1));

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

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

        for (int v : g[p[u]][b[u] % p[u]]){
            if (d[v] > d[u] + abs(b[u] - b[v]) / p[u]){
                d[v] = d[u] + abs(b[u] - b[v]) / p[u];
                q.push(make_pair(d[v], v));
            }
        }
    }

    if (d[2] >= inf) cout << -1;
    else cout << d[2];
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94624 KB Output is correct
2 Correct 50 ms 94756 KB Output is correct
3 Correct 51 ms 94660 KB Output is correct
4 Correct 46 ms 94720 KB Output is correct
5 Correct 49 ms 94600 KB Output is correct
6 Correct 48 ms 94660 KB Output is correct
7 Correct 50 ms 94804 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94600 KB Output is correct
2 Correct 49 ms 94604 KB Output is correct
3 Correct 50 ms 94600 KB Output is correct
4 Correct 56 ms 94660 KB Output is correct
5 Correct 49 ms 94648 KB Output is correct
6 Correct 47 ms 94680 KB Output is correct
7 Correct 49 ms 94660 KB Output is correct
8 Correct 47 ms 94708 KB Output is correct
9 Correct 46 ms 94660 KB Output is correct
10 Correct 50 ms 95036 KB Output is correct
11 Correct 60 ms 96072 KB Output is correct
12 Correct 80 ms 95616 KB Output is correct
13 Correct 68 ms 94788 KB Output is correct
14 Correct 57 ms 95556 KB Output is correct
15 Correct 52 ms 95648 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94716 KB Output is correct
2 Correct 46 ms 94680 KB Output is correct
3 Correct 48 ms 94708 KB Output is correct
4 Correct 49 ms 94632 KB Output is correct
5 Correct 46 ms 94724 KB Output is correct
6 Correct 48 ms 94668 KB Output is correct
7 Correct 48 ms 94604 KB Output is correct
8 Correct 49 ms 94740 KB Output is correct
9 Correct 52 ms 94716 KB Output is correct
10 Correct 54 ms 95028 KB Output is correct
11 Correct 56 ms 96028 KB Output is correct
12 Correct 76 ms 95632 KB Output is correct
13 Correct 74 ms 94760 KB Output is correct
14 Correct 57 ms 95784 KB Output is correct
15 Correct 54 ms 95596 KB Output is correct
16 Correct 59 ms 95924 KB Output is correct
17 Correct 114 ms 101012 KB Output is correct
18 Correct 411 ms 130124 KB Output is correct
19 Correct 247 ms 118388 KB Output is correct
20 Correct 78 ms 94776 KB Output is correct
21 Correct 394 ms 119084 KB Output is correct
22 Correct 312 ms 123028 KB Output is correct
23 Correct 423 ms 129500 KB Output is correct
24 Correct 796 ms 145800 KB Output is correct
25 Correct 818 ms 147784 KB Output is correct
26 Correct 77 ms 96708 KB Output is correct
27 Correct 269 ms 114684 KB Output is correct
28 Correct 858 ms 160740 KB Output is correct
29 Correct 48 ms 94892 KB Output is correct
30 Correct 50 ms 94764 KB Output is correct
31 Correct 50 ms 94820 KB Output is correct
32 Correct 51 ms 94840 KB Output is correct
33 Correct 59 ms 95664 KB Output is correct
34 Correct 58 ms 95556 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94616 KB Output is correct
2 Correct 47 ms 94640 KB Output is correct
3 Correct 50 ms 94708 KB Output is correct
4 Correct 50 ms 94660 KB Output is correct
5 Correct 52 ms 94640 KB Output is correct
6 Correct 51 ms 94656 KB Output is correct
7 Correct 49 ms 94712 KB Output is correct
8 Correct 52 ms 94688 KB Output is correct
9 Correct 51 ms 94788 KB Output is correct
10 Correct 54 ms 95072 KB Output is correct
11 Correct 56 ms 96032 KB Output is correct
12 Correct 73 ms 95636 KB Output is correct
13 Correct 70 ms 94720 KB Output is correct
14 Correct 51 ms 95620 KB Output is correct
15 Correct 57 ms 95672 KB Output is correct
16 Correct 59 ms 95924 KB Output is correct
17 Correct 114 ms 101184 KB Output is correct
18 Correct 413 ms 130168 KB Output is correct
19 Correct 248 ms 118408 KB Output is correct
20 Correct 75 ms 94788 KB Output is correct
21 Correct 385 ms 119164 KB Output is correct
22 Correct 338 ms 123204 KB Output is correct
23 Correct 410 ms 129484 KB Output is correct
24 Correct 772 ms 145860 KB Output is correct
25 Correct 815 ms 147780 KB Output is correct
26 Correct 79 ms 96708 KB Output is correct
27 Correct 278 ms 114708 KB Output is correct
28 Correct 853 ms 160820 KB Output is correct
29 Correct 53 ms 94916 KB Output is correct
30 Correct 46 ms 94676 KB Output is correct
31 Correct 50 ms 94932 KB Output is correct
32 Correct 51 ms 94916 KB Output is correct
33 Correct 54 ms 95584 KB Output is correct
34 Correct 52 ms 95680 KB Output is correct
35 Execution timed out 1091 ms 161816 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94732 KB Output is correct
2 Correct 51 ms 94660 KB Output is correct
3 Correct 47 ms 94632 KB Output is correct
4 Correct 52 ms 94636 KB Output is correct
5 Correct 50 ms 94692 KB Output is correct
6 Correct 47 ms 94716 KB Output is correct
7 Correct 46 ms 94712 KB Output is correct
8 Correct 50 ms 94712 KB Output is correct
9 Correct 51 ms 94728 KB Output is correct
10 Correct 53 ms 95056 KB Output is correct
11 Correct 60 ms 96076 KB Output is correct
12 Correct 73 ms 95536 KB Output is correct
13 Correct 72 ms 94716 KB Output is correct
14 Correct 63 ms 95556 KB Output is correct
15 Correct 55 ms 95612 KB Output is correct
16 Correct 60 ms 95932 KB Output is correct
17 Correct 116 ms 101200 KB Output is correct
18 Correct 413 ms 130156 KB Output is correct
19 Correct 241 ms 118340 KB Output is correct
20 Correct 74 ms 94804 KB Output is correct
21 Correct 367 ms 119104 KB Output is correct
22 Correct 314 ms 123020 KB Output is correct
23 Correct 408 ms 129544 KB Output is correct
24 Correct 747 ms 145988 KB Output is correct
25 Correct 822 ms 147784 KB Output is correct
26 Correct 76 ms 96708 KB Output is correct
27 Correct 273 ms 114684 KB Output is correct
28 Correct 900 ms 160708 KB Output is correct
29 Correct 50 ms 94920 KB Output is correct
30 Correct 52 ms 94660 KB Output is correct
31 Correct 53 ms 94836 KB Output is correct
32 Correct 52 ms 94892 KB Output is correct
33 Correct 51 ms 95664 KB Output is correct
34 Correct 57 ms 95660 KB Output is correct
35 Execution timed out 1093 ms 161096 KB Time limit exceeded
36 Halted 0 ms 0 KB -