oj.uz

Submission #960690

# Submission time Handle Problem Language Result Execution time Memory
960690 2024-04-10T23:30:04 Z 3omar_ahmed Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
 563 ms 148176 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 = 30004 * 175, M = 175;
vector < int > dis(N, 1e9);
vector < vector < pair < int , int >>> adj(N);
int conv(int i, int j, int n) {
    return (i * M + j);
}
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);
    set < pair < int , int >> s;
    for(int i = 0 ; i < m ; i++) {
        int a, b;
        cin >> a >> b;
        if(b < n) s.insert({a, b});
        if(i == 0) {
            first = {a, b};
        } else if(i == 1) {
            second = {a, b};
        }
    }
    for(auto i : s) {
        arr[i.first].push_back(i.second);
    }
    int st = first.first * M;
    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;
        int i = top.second / M;
        int j = top.second % M;
        // cout << i << " " << j << " " << top.first << endl;
        if(j == 0) {
            for(auto nxt : arr[i]) {
                if(nxt < M && dis[conv(i, nxt, n)] > top.first) {
                    dis[conv(i, nxt, n)] = top.first;
                    pq.push({-dis[conv(i, nxt, n)], conv(i, nxt, n)});
                } else if(nxt >= M) {
                    for(int j = 1 ; j <= n ; j++) {
                        if(i + j * nxt < n && dis[conv(i + j * nxt, 0, n)] > top.first + j) {
                            dis[conv(i + j * nxt, 0, n)] = top.first + j;
                            pq.push({-dis[conv(i + j * nxt, 0, n)], conv(i + j * nxt, 0, n)});
                        }
                        if(i + j * nxt >= n) break;
                    }
                    for(int j = 1 ; j <= n ; j++) {
                        if(i - j * nxt >= 0 && dis[conv(i - j * nxt, 0, n)] > top.first + j) {
                            dis[conv(i - j * nxt, 0, n)] = top.first + j;
                            pq.push({-dis[conv(i - j * nxt, 0, n)], conv(i - j * nxt, 0, n)});
                        }
                        if(i - j * nxt < 0) break;
                    }
                }
            }
        } else {
            if(i + j < n && dis[conv(i + j, j, n)] > top.first + 1) {
                dis[conv(i + j, j, n)] = top.first + 1;
                pq.push({-dis[conv(i + j, j, n)], conv(i + j, j, n)});
            }
            if(i + j < n && dis[conv(i + j, 0, n)] > top.first + 1) {
                dis[conv(i + j, 0, n)] = top.first + 1;
                pq.push({-dis[conv(i + j, 0, n)], conv(i + j, 0, n)});
            }
            if(i - j >= 0 && dis[conv(i - j, j, n)] > top.first + 1) {
                dis[conv(i - j, j, n)] = top.first + 1;
                pq.push({-dis[conv(i - j, j, n)], conv(i - j, j, n)});
            }
            if(i - j >= 0 && dis[conv(i - j, 0, n)] > top.first + 1) {
                dis[conv(i - j, 0, n)] = top.first + 1;
                pq.push({-dis[conv(i - j, 0, n)], conv(i - j, 0, n)});
            }
        }
    }
    int ans = 1e9;
    for(int i = 0 ; i < M ; i++) {
        ans = min(ans, dis[second.first * M + i]);
    }
    if(ans >= 1e8) ans = -1;
    cout << ans << endl;
    return 0 ;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 144104 KB Output is correct
2 Correct 34 ms 144072 KB Output is correct
3 Correct 33 ms 144208 KB Output is correct
4 Correct 33 ms 144216 KB Output is correct
5 Correct 33 ms 144220 KB Output is correct
6 Correct 33 ms 144304 KB Output is correct
7 Correct 33 ms 144320 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 144216 KB Output is correct
2 Correct 33 ms 144216 KB Output is correct
3 Correct 34 ms 144220 KB Output is correct
4 Correct 35 ms 144200 KB Output is correct
5 Correct 34 ms 144220 KB Output is correct
6 Correct 35 ms 144296 KB Output is correct
7 Correct 33 ms 144220 KB Output is correct
8 Correct 34 ms 144212 KB Output is correct
9 Correct 33 ms 144472 KB Output is correct
10 Correct 34 ms 144212 KB Output is correct
11 Correct 35 ms 144424 KB Output is correct
12 Correct 33 ms 144240 KB Output is correct
13 Correct 34 ms 144216 KB Output is correct
14 Correct 34 ms 144220 KB Output is correct
15 Correct 34 ms 144220 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 144296 KB Output is correct
2 Correct 35 ms 144224 KB Output is correct
3 Correct 34 ms 144208 KB Output is correct
4 Correct 34 ms 144320 KB Output is correct
5 Correct 33 ms 144288 KB Output is correct
6 Correct 33 ms 144220 KB Output is correct
7 Correct 35 ms 144220 KB Output is correct
8 Correct 34 ms 144208 KB Output is correct
9 Correct 33 ms 144080 KB Output is correct
10 Correct 33 ms 144220 KB Output is correct
11 Correct 35 ms 144292 KB Output is correct
12 Correct 35 ms 144208 KB Output is correct
13 Correct 38 ms 144288 KB Output is correct
14 Correct 36 ms 144440 KB Output is correct
15 Correct 34 ms 144220 KB Output is correct
16 Correct 34 ms 144120 KB Output is correct
17 Correct 35 ms 144216 KB Output is correct
18 Correct 34 ms 144220 KB Output is correct
19 Correct 34 ms 144216 KB Output is correct
20 Correct 35 ms 144464 KB Output is correct
21 Correct 34 ms 144308 KB Output is correct
22 Correct 34 ms 144388 KB Output is correct
23 Correct 35 ms 144212 KB Output is correct
24 Correct 37 ms 144452 KB Output is correct
25 Correct 35 ms 144412 KB Output is correct
26 Correct 38 ms 144212 KB Output is correct
27 Correct 38 ms 144576 KB Output is correct
28 Correct 35 ms 144264 KB Output is correct
29 Correct 38 ms 144208 KB Output is correct
30 Correct 34 ms 144244 KB Output is correct
31 Correct 36 ms 144368 KB Output is correct
32 Correct 38 ms 144220 KB Output is correct
33 Correct 45 ms 144512 KB Output is correct
34 Correct 44 ms 144476 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 144116 KB Output is correct
2 Correct 34 ms 144216 KB Output is correct
3 Correct 34 ms 144208 KB Output is correct
4 Correct 34 ms 144220 KB Output is correct
5 Correct 34 ms 144252 KB Output is correct
6 Correct 35 ms 144208 KB Output is correct
7 Correct 33 ms 144208 KB Output is correct
8 Correct 33 ms 144208 KB Output is correct
9 Correct 34 ms 144088 KB Output is correct
10 Correct 32 ms 144216 KB Output is correct
11 Correct 35 ms 144220 KB Output is correct
12 Correct 37 ms 144220 KB Output is correct
13 Correct 34 ms 144220 KB Output is correct
14 Correct 38 ms 144348 KB Output is correct
15 Correct 37 ms 144216 KB Output is correct
16 Correct 33 ms 144208 KB Output is correct
17 Correct 35 ms 144256 KB Output is correct
18 Correct 34 ms 144212 KB Output is correct
19 Correct 33 ms 144216 KB Output is correct
20 Correct 37 ms 144660 KB Output is correct
21 Correct 33 ms 144220 KB Output is correct
22 Correct 34 ms 144220 KB Output is correct
23 Correct 34 ms 144208 KB Output is correct
24 Correct 35 ms 144464 KB Output is correct
25 Correct 34 ms 144476 KB Output is correct
26 Correct 37 ms 144476 KB Output is correct
27 Correct 33 ms 144208 KB Output is correct
28 Correct 34 ms 144472 KB Output is correct
29 Correct 37 ms 144232 KB Output is correct
30 Correct 34 ms 144220 KB Output is correct
31 Correct 35 ms 144264 KB Output is correct
32 Correct 35 ms 144216 KB Output is correct
33 Correct 45 ms 144380 KB Output is correct
34 Correct 42 ms 144472 KB Output is correct
35 Correct 45 ms 145348 KB Output is correct
36 Correct 35 ms 144728 KB Output is correct
37 Correct 52 ms 145408 KB Output is correct
38 Correct 54 ms 146048 KB Output is correct
39 Correct 52 ms 146004 KB Output is correct
40 Correct 52 ms 146008 KB Output is correct
41 Correct 57 ms 146012 KB Output is correct
42 Correct 38 ms 144188 KB Output is correct
43 Correct 36 ms 144220 KB Output is correct
44 Correct 39 ms 144432 KB Output is correct
45 Correct 80 ms 146260 KB Output is correct
46 Correct 74 ms 146260 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 144220 KB Output is correct
2 Correct 33 ms 144220 KB Output is correct
3 Correct 35 ms 144220 KB Output is correct
4 Correct 34 ms 144228 KB Output is correct
5 Correct 34 ms 144420 KB Output is correct
6 Correct 33 ms 144220 KB Output is correct
7 Correct 35 ms 144052 KB Output is correct
8 Correct 33 ms 144300 KB Output is correct
9 Correct 33 ms 144220 KB Output is correct
10 Correct 37 ms 144220 KB Output is correct
11 Correct 34 ms 144208 KB Output is correct
12 Correct 34 ms 144208 KB Output is correct
13 Correct 35 ms 144220 KB Output is correct
14 Correct 34 ms 144276 KB Output is correct
15 Correct 34 ms 144208 KB Output is correct
16 Correct 33 ms 144208 KB Output is correct
17 Correct 37 ms 144208 KB Output is correct
18 Correct 38 ms 144648 KB Output is correct
19 Correct 35 ms 144220 KB Output is correct
20 Correct 34 ms 144268 KB Output is correct
21 Correct 33 ms 144324 KB Output is correct
22 Correct 35 ms 144220 KB Output is correct
23 Correct 34 ms 144220 KB Output is correct
24 Correct 35 ms 144476 KB Output is correct
25 Correct 36 ms 144728 KB Output is correct
26 Correct 35 ms 144216 KB Output is correct
27 Correct 34 ms 144160 KB Output is correct
28 Correct 35 ms 144464 KB Output is correct
29 Correct 37 ms 144220 KB Output is correct
30 Correct 35 ms 144360 KB Output is correct
31 Correct 36 ms 144212 KB Output is correct
32 Correct 34 ms 144248 KB Output is correct
33 Correct 48 ms 144540 KB Output is correct
34 Correct 45 ms 144504 KB Output is correct
35 Correct 50 ms 145428 KB Output is correct
36 Correct 36 ms 144464 KB Output is correct
37 Correct 55 ms 145512 KB Output is correct
38 Correct 52 ms 146056 KB Output is correct
39 Correct 54 ms 146052 KB Output is correct
40 Correct 53 ms 146012 KB Output is correct
41 Correct 52 ms 146000 KB Output is correct
42 Correct 38 ms 144208 KB Output is correct
43 Correct 37 ms 144216 KB Output is correct
44 Correct 37 ms 144468 KB Output is correct
45 Correct 84 ms 146244 KB Output is correct
46 Correct 74 ms 146256 KB Output is correct
47 Correct 87 ms 146384 KB Output is correct
48 Correct 47 ms 146396 KB Output is correct
49 Correct 41 ms 146260 KB Output is correct
50 Correct 39 ms 146012 KB Output is correct
51 Correct 73 ms 147536 KB Output is correct
52 Correct 75 ms 147540 KB Output is correct
53 Correct 59 ms 147280 KB Output is correct
54 Correct 35 ms 144972 KB Output is correct
55 Correct 36 ms 144988 KB Output is correct
56 Correct 46 ms 147540 KB Output is correct
57 Correct 87 ms 145240 KB Output is correct
58 Correct 40 ms 144892 KB Output is correct
59 Correct 47 ms 145236 KB Output is correct
60 Correct 46 ms 145244 KB Output is correct
61 Correct 43 ms 145196 KB Output is correct
62 Correct 66 ms 147672 KB Output is correct
63 Correct 66 ms 147416 KB Output is correct
64 Correct 71 ms 147304 KB Output is correct
65 Correct 186 ms 147960 KB Output is correct
66 Correct 563 ms 147832 KB Output is correct
67 Correct 558 ms 148176 KB Output is correct