oj.uz

Submission #953634

# Submission time Handle Problem Language Result Execution time Memory
953634 2024-03-26T11:27:21 Z Unforgettablepl Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 68 ms 137148 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

priority_queue<pair<int,pair<int,int>>> q;
vector<pair<pair<int,int>,int>> adj[30000][174];
bool visited[30000][174];
int n;
const int threshold = 173;

void adddoge(int power,int building){
    if(power>threshold){
        int minimum = building - power*(building/power);
        for (int i = minimum; i < n; i += power)
            adj[building][0].emplace_back(make_pair(i,0),1);
    } else {
        adj[building][0].emplace_back(make_pair(building,power),0);
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    cin >> n >> m;
    int base,tar,bp,tp;
    cin>>base>>bp>>tar>>tp;
    adddoge(bp,base);
    adddoge(tp,tar);
    for(int i=2;i<m;i++){
        int b,p;cin>>b>>p;
        adddoge(p,b);
    }
    for(int i=0;i<n;i++){
        for(int j=1;j<174;j++){
            adj[i][j].emplace_back(make_pair(i,0),0);
        }
    }
    for(int power=1;power<=173;power++){
        for(int i=power;i<n;i++){
            adj[i][power].emplace_back(make_pair(i-power,power),1);
        }
        for(int i=n-power-1;i>=0;i--){
            adj[i][power].emplace_back(make_pair(i+power,power),1);
        }
    }
    q.emplace(0, make_pair(base,0));
    while(!q.empty()){
        auto curr = q.top();q.pop();
        if(visited[curr.second.first][curr.second.second])continue;
        visited[curr.second.first][curr.second.second]=true;
        if(curr.second.first==tar){
            cout << -curr.first << '\n';
            return 0;
        }
        for(auto&i:adj[curr.second.first][curr.second.second])if(!visited[i.first.first][i.first.second])q.emplace(curr.first-i.second,i.first);
    }
    cout << "-1\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 123732 KB Output is correct
2 Correct 44 ms 123996 KB Output is correct
3 Correct 38 ms 123736 KB Output is correct
4 Correct 37 ms 123696 KB Output is correct
5 Correct 37 ms 123860 KB Output is correct
6 Correct 38 ms 123740 KB Output is correct
7 Correct 38 ms 123756 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 123732 KB Output is correct
2 Correct 42 ms 123716 KB Output is correct
3 Correct 37 ms 123732 KB Output is correct
4 Correct 43 ms 123752 KB Output is correct
5 Correct 37 ms 123912 KB Output is correct
6 Correct 37 ms 123736 KB Output is correct
7 Correct 36 ms 123740 KB Output is correct
8 Correct 37 ms 123904 KB Output is correct
9 Correct 37 ms 124248 KB Output is correct
10 Correct 39 ms 124752 KB Output is correct
11 Correct 39 ms 124884 KB Output is correct
12 Correct 40 ms 124752 KB Output is correct
13 Correct 39 ms 124752 KB Output is correct
14 Correct 41 ms 124764 KB Output is correct
15 Correct 41 ms 124760 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 123808 KB Output is correct
2 Correct 37 ms 123740 KB Output is correct
3 Correct 37 ms 123732 KB Output is correct
4 Correct 38 ms 123728 KB Output is correct
5 Correct 38 ms 123844 KB Output is correct
6 Correct 38 ms 123736 KB Output is correct
7 Correct 37 ms 123740 KB Output is correct
8 Correct 38 ms 123996 KB Output is correct
9 Correct 39 ms 124240 KB Output is correct
10 Correct 39 ms 124764 KB Output is correct
11 Correct 40 ms 124752 KB Output is correct
12 Correct 42 ms 125208 KB Output is correct
13 Correct 39 ms 124752 KB Output is correct
14 Correct 40 ms 124756 KB Output is correct
15 Correct 40 ms 124764 KB Output is correct
16 Correct 46 ms 126344 KB Output is correct
17 Incorrect 68 ms 137024 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 123736 KB Output is correct
2 Correct 37 ms 123664 KB Output is correct
3 Correct 37 ms 123900 KB Output is correct
4 Correct 38 ms 123992 KB Output is correct
5 Correct 38 ms 123740 KB Output is correct
6 Correct 37 ms 123740 KB Output is correct
7 Correct 40 ms 123860 KB Output is correct
8 Correct 39 ms 124120 KB Output is correct
9 Correct 38 ms 124180 KB Output is correct
10 Correct 39 ms 124760 KB Output is correct
11 Correct 39 ms 124828 KB Output is correct
12 Correct 41 ms 124616 KB Output is correct
13 Correct 39 ms 124708 KB Output is correct
14 Correct 41 ms 124804 KB Output is correct
15 Correct 40 ms 124768 KB Output is correct
16 Correct 42 ms 126384 KB Output is correct
17 Incorrect 66 ms 137148 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 123736 KB Output is correct
2 Correct 41 ms 123848 KB Output is correct
3 Correct 37 ms 123740 KB Output is correct
4 Correct 41 ms 123712 KB Output is correct
5 Correct 37 ms 123812 KB Output is correct
6 Correct 37 ms 123732 KB Output is correct
7 Correct 38 ms 123732 KB Output is correct
8 Correct 39 ms 124384 KB Output is correct
9 Correct 39 ms 124240 KB Output is correct
10 Correct 42 ms 124752 KB Output is correct
11 Correct 40 ms 124752 KB Output is correct
12 Correct 41 ms 124764 KB Output is correct
13 Correct 39 ms 124764 KB Output is correct
14 Correct 40 ms 124976 KB Output is correct
15 Correct 41 ms 124752 KB Output is correct
16 Correct 42 ms 126384 KB Output is correct
17 Incorrect 64 ms 137024 KB Output isn't correct
18 Halted 0 ms 0 KB -