oj.uz

Submission #976218

# Submission time Handle Problem Language Result Execution time Memory
976218 2024-05-06T09:54:29 Z SuPythony Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 1000 ms 64608 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
    int n,m; cin>>n>>m;
    vector<pair<int,int>> doges;
    for (int i=0; i<m; i++) {
        int b,p; cin>>b>>p;
        doges.push_back({b,p});
    }
    vector<vector<pair<int,ll>>> al(m,vector<pair<int,ll>>());
    for (int i=0; i<m; i++) {
        if (i==1) continue;
        for (int j=0; j<m; j++) {
            if (i==j) continue;
            int d=abs(doges[i].first-doges[j].first);
            if (d%doges[i].second==0) {
                al[i].push_back({j,d/doges[i].second});
            }
        }
    }
    vector<ll> dist(m,1e18);
    dist[0]=0;
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<>> p;
    p.push({0ll,0});
    while (!p.empty()) {
        int t=p.top().second; p.pop();
        for (auto v: al[t]) {
            if (dist[t]+v.second<dist[v.first]) {
                dist[v.first]=dist[t]+v.second;
                p.push({dist[v.first],v.first});
            }
        }
    }
    if (dist[1]==1e18) cout<<-1;
    else cout<<dist[1];
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 756 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 24 ms 4676 KB Output is correct
12 Correct 66 ms 64132 KB Output is correct
13 Correct 67 ms 64484 KB Output is correct
14 Correct 22 ms 3244 KB Output is correct
15 Correct 22 ms 3296 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 440 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 23 ms 4712 KB Output is correct
12 Correct 66 ms 64084 KB Output is correct
13 Correct 67 ms 64580 KB Output is correct
14 Correct 22 ms 3432 KB Output is correct
15 Correct 22 ms 3420 KB Output is correct
16 Correct 4 ms 860 KB Output is correct
17 Correct 17 ms 1628 KB Output is correct
18 Correct 5 ms 348 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 67 ms 64608 KB Output is correct
21 Correct 7 ms 604 KB Output is correct
22 Correct 3 ms 348 KB Output is correct
23 Correct 5 ms 496 KB Output is correct
24 Correct 17 ms 856 KB Output is correct
25 Correct 19 ms 600 KB Output is correct
26 Correct 63 ms 58560 KB Output is correct
27 Correct 64 ms 60352 KB Output is correct
28 Correct 19 ms 856 KB Output is correct
29 Correct 4 ms 856 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 3 ms 524 KB Output is correct
32 Correct 2 ms 604 KB Output is correct
33 Correct 22 ms 3292 KB Output is correct
34 Correct 23 ms 3420 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 0 ms 440 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 24 ms 4700 KB Output is correct
12 Correct 67 ms 64084 KB Output is correct
13 Correct 69 ms 64456 KB Output is correct
14 Correct 23 ms 3404 KB Output is correct
15 Correct 22 ms 3244 KB Output is correct
16 Correct 5 ms 856 KB Output is correct
17 Correct 17 ms 1628 KB Output is correct
18 Correct 5 ms 344 KB Output is correct
19 Correct 2 ms 436 KB Output is correct
20 Correct 68 ms 64508 KB Output is correct
21 Correct 7 ms 600 KB Output is correct
22 Correct 3 ms 348 KB Output is correct
23 Correct 5 ms 444 KB Output is correct
24 Correct 17 ms 860 KB Output is correct
25 Correct 19 ms 604 KB Output is correct
26 Correct 62 ms 58488 KB Output is correct
27 Correct 64 ms 60244 KB Output is correct
28 Correct 19 ms 860 KB Output is correct
29 Correct 4 ms 952 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 2 ms 604 KB Output is correct
33 Correct 22 ms 3420 KB Output is correct
34 Correct 22 ms 3412 KB Output is correct
35 Execution timed out 1042 ms 22408 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 556 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 23 ms 4696 KB Output is correct
12 Correct 68 ms 64084 KB Output is correct
13 Correct 69 ms 64584 KB Output is correct
14 Correct 22 ms 3324 KB Output is correct
15 Correct 22 ms 3332 KB Output is correct
16 Correct 5 ms 860 KB Output is correct
17 Correct 17 ms 1604 KB Output is correct
18 Correct 5 ms 348 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 66 ms 64596 KB Output is correct
21 Correct 7 ms 600 KB Output is correct
22 Correct 3 ms 348 KB Output is correct
23 Correct 5 ms 348 KB Output is correct
24 Correct 17 ms 852 KB Output is correct
25 Correct 19 ms 604 KB Output is correct
26 Correct 62 ms 58504 KB Output is correct
27 Correct 65 ms 60244 KB Output is correct
28 Correct 20 ms 860 KB Output is correct
29 Correct 4 ms 860 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 2 ms 516 KB Output is correct
32 Correct 2 ms 604 KB Output is correct
33 Correct 23 ms 3232 KB Output is correct
34 Correct 23 ms 3420 KB Output is correct
35 Execution timed out 1076 ms 22700 KB Time limit exceeded
36 Halted 0 ms 0 KB -