oj.uz

Submission #975809

# Submission time Handle Problem Language Result Execution time Memory
975809 2024-05-05T22:58:32 Z andro Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 185 ms 262144 KB 
#include <bits/stdc++.h>

#define int long long

#define ll long long

using namespace std;

const int N = 30005;

vector<pair<ll,ll>>G[N];
vector<ll>dist(N,1e18),par(N,-1);
vector<int> jump[N];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> a(m);
    for(int i = 0; i < m; i++) {
        cin >> a[i].first >> a[i].second;
        jump[a[i].first].push_back(a[i].second);
    }
    for(int i = 0; i < n; i++) {
        for(auto it : jump[i]) {
            int cnt = 1;
            for(int j = i - it; j >= 0; j -= it) {
                G[i].push_back({j, cnt});
                cnt += 1;
            }
            cnt = 1;
            for(int j = i + it; j < n; j += it) {
                G[i].push_back({j, cnt});
                cnt += 1;
            }
        }
    }
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;
    pq.push({0,a[0].first});
    dist[a[0].first] = 0;
    vector<bool>vis(n+1,false);
    while(pq.size()) {
        ll d,u;
        tie(d,u) = pq.top();
        pq.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(auto X:G[u]) {
            if(dist[X.first] > dist[u] + X.second) {
                dist[X.first] = dist[u] + X.second;
                pq.push({dist[X.first],X.first});
                par[X.first] = u;
            }
        }
    }
    if(dist[a[1].first] == 1e18) {
        cout << - 1;
    }
    else {
        cout << dist[a[1].first];
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2140 KB Output is correct
2 Correct 1 ms 2136 KB Output is correct
3 Correct 1 ms 2136 KB Output is correct
4 Correct 1 ms 2140 KB Output is correct
5 Correct 1 ms 2140 KB Output is correct
6 Correct 1 ms 2140 KB Output is correct
7 Correct 1 ms 2140 KB Output is correct
8 Correct 1 ms 2136 KB Output is correct
9 Correct 1 ms 2136 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 5 ms 6860 KB Output is correct
13 Correct 5 ms 7892 KB Output is correct
14 Correct 2 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2140 KB Output is correct
2 Correct 1 ms 2136 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2140 KB Output is correct
5 Correct 1 ms 2140 KB Output is correct
6 Correct 1 ms 2140 KB Output is correct
7 Correct 1 ms 2140 KB Output is correct
8 Correct 2 ms 2140 KB Output is correct
9 Correct 1 ms 2140 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 2 ms 2492 KB Output is correct
12 Correct 6 ms 8396 KB Output is correct
13 Correct 5 ms 7892 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 2 ms 2908 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 2 ms 2396 KB Output is correct
20 Correct 69 ms 66732 KB Output is correct
21 Correct 1 ms 2392 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 2 ms 2396 KB Output is correct
24 Correct 2 ms 2652 KB Output is correct
25 Correct 2 ms 2652 KB Output is correct
26 Correct 65 ms 69932 KB Output is correct
27 Correct 53 ms 68516 KB Output is correct
28 Correct 2 ms 2656 KB Output is correct
29 Correct 3 ms 3680 KB Output is correct
30 Correct 2 ms 2912 KB Output is correct
31 Correct 3 ms 3080 KB Output is correct
32 Correct 2 ms 2912 KB Output is correct
33 Correct 5 ms 4828 KB Output is correct
34 Correct 5 ms 4892 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2144 KB Output is correct
2 Correct 1 ms 2328 KB Output is correct
3 Correct 1 ms 2144 KB Output is correct
4 Correct 1 ms 2144 KB Output is correct
5 Correct 1 ms 2140 KB Output is correct
6 Correct 1 ms 2144 KB Output is correct
7 Correct 1 ms 2144 KB Output is correct
8 Correct 1 ms 2148 KB Output is correct
9 Correct 1 ms 2144 KB Output is correct
10 Correct 1 ms 2408 KB Output is correct
11 Correct 2 ms 2408 KB Output is correct
12 Correct 5 ms 7812 KB Output is correct
13 Correct 5 ms 7660 KB Output is correct
14 Correct 2 ms 2408 KB Output is correct
15 Correct 1 ms 2400 KB Output is correct
16 Correct 1 ms 2404 KB Output is correct
17 Correct 2 ms 2920 KB Output is correct
18 Correct 1 ms 2408 KB Output is correct
19 Correct 2 ms 2408 KB Output is correct
20 Correct 65 ms 66656 KB Output is correct
21 Correct 1 ms 2408 KB Output is correct
22 Correct 1 ms 2404 KB Output is correct
23 Correct 2 ms 2408 KB Output is correct
24 Correct 2 ms 2660 KB Output is correct
25 Correct 2 ms 2664 KB Output is correct
26 Correct 56 ms 69404 KB Output is correct
27 Correct 54 ms 68984 KB Output is correct
28 Correct 2 ms 2664 KB Output is correct
29 Correct 4 ms 3688 KB Output is correct
30 Correct 2 ms 2920 KB Output is correct
31 Correct 3 ms 3172 KB Output is correct
32 Correct 2 ms 2920 KB Output is correct
33 Correct 5 ms 4836 KB Output is correct
34 Correct 5 ms 4836 KB Output is correct
35 Correct 8 ms 6168 KB Output is correct
36 Correct 3 ms 2920 KB Output is correct
37 Correct 10 ms 9064 KB Output is correct
38 Correct 11 ms 8296 KB Output is correct
39 Correct 11 ms 8552 KB Output is correct
40 Correct 12 ms 8280 KB Output is correct
41 Correct 11 ms 8292 KB Output is correct
42 Runtime error 185 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 1 ms 2152 KB Output is correct
2 Correct 1 ms 2152 KB Output is correct
3 Correct 1 ms 2152 KB Output is correct
4 Correct 2 ms 2148 KB Output is correct
5 Correct 1 ms 2152 KB Output is correct
6 Correct 1 ms 2164 KB Output is correct
7 Correct 1 ms 2144 KB Output is correct
8 Correct 1 ms 2144 KB Output is correct
9 Correct 1 ms 2144 KB Output is correct
10 Correct 1 ms 2404 KB Output is correct
11 Correct 1 ms 2400 KB Output is correct
12 Correct 5 ms 7120 KB Output is correct
13 Correct 5 ms 7132 KB Output is correct
14 Correct 2 ms 2400 KB Output is correct
15 Correct 2 ms 2404 KB Output is correct
16 Correct 1 ms 2404 KB Output is correct
17 Correct 2 ms 2912 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2400 KB Output is correct
20 Correct 65 ms 66508 KB Output is correct
21 Correct 2 ms 2404 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 3 ms 2400 KB Output is correct
24 Correct 2 ms 2656 KB Output is correct
25 Correct 2 ms 2656 KB Output is correct
26 Correct 57 ms 69328 KB Output is correct
27 Correct 53 ms 69032 KB Output is correct
28 Correct 2 ms 2836 KB Output is correct
29 Correct 4 ms 3676 KB Output is correct
30 Correct 2 ms 3160 KB Output is correct
31 Correct 3 ms 3120 KB Output is correct
32 Correct 2 ms 2908 KB Output is correct
33 Correct 5 ms 4824 KB Output is correct
34 Correct 5 ms 4824 KB Output is correct
35 Correct 8 ms 6232 KB Output is correct
36 Correct 3 ms 2904 KB Output is correct
37 Correct 10 ms 9052 KB Output is correct
38 Correct 11 ms 8284 KB Output is correct
39 Correct 12 ms 8704 KB Output is correct
40 Correct 12 ms 8436 KB Output is correct
41 Correct 11 ms 8028 KB Output is correct
42 Runtime error 137 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -