oj.uz

Submission #953630

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

#define int long long

priority_queue<pair<int,int>> q;
vector<pair<int,int>> adj[6000000];
bool visited[6000000];
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*174].emplace_back(i*174,1);
    } else {
        adj[building*174].emplace_back(building*174+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++){
        int b = i*174;
        for(int j=b+1;j<b+174;j++){
            adj[j].emplace_back(b,0);
        }
    }
    for(int power=1;power<=173;power++){
        int offset = 174*power;
        for(int i=power;i<n;i++){
            adj[i*174+power].emplace_back(i*174+power-offset,1);
        }
        for(int i=n-power-1;i>=0;i--){
            adj[i*174+power].emplace_back(i*174+power+offset,1);
        }
    }
    base*=174;tar*=174;
    q.emplace(0, base);
    while(!q.empty()){
        auto curr = q.top();q.pop();
        if(visited[curr.second])continue;
        visited[curr.second]=true;
        if(curr.second==tar){
            cout << -curr.first << '\n';
            return 0;
        }
        for(auto&i:adj[curr.second])if(!visited[i.first])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 70 ms 142828 KB Output is correct
2 Correct 45 ms 142676 KB Output is correct
3 Correct 45 ms 142932 KB Output is correct
4 Correct 44 ms 142888 KB Output is correct
5 Correct 46 ms 142940 KB Output is correct
6 Correct 47 ms 142936 KB Output is correct
7 Correct 48 ms 142924 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 142820 KB Output is correct
2 Correct 44 ms 142676 KB Output is correct
3 Correct 46 ms 142940 KB Output is correct
4 Correct 46 ms 142868 KB Output is correct
5 Correct 45 ms 142928 KB Output is correct
6 Correct 45 ms 142928 KB Output is correct
7 Correct 45 ms 142928 KB Output is correct
8 Correct 46 ms 142960 KB Output is correct
9 Correct 46 ms 143316 KB Output is correct
10 Correct 51 ms 143564 KB Output is correct
11 Correct 47 ms 143640 KB Output is correct
12 Correct 52 ms 143840 KB Output is correct
13 Correct 52 ms 143760 KB Output is correct
14 Correct 47 ms 143728 KB Output is correct
15 Correct 50 ms 143688 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 142796 KB Output is correct
2 Correct 45 ms 142952 KB Output is correct
3 Correct 51 ms 142940 KB Output is correct
4 Correct 47 ms 142836 KB Output is correct
5 Correct 45 ms 142928 KB Output is correct
6 Correct 45 ms 142932 KB Output is correct
7 Correct 45 ms 142892 KB Output is correct
8 Correct 46 ms 143072 KB Output is correct
9 Correct 46 ms 143452 KB Output is correct
10 Correct 47 ms 143704 KB Output is correct
11 Correct 46 ms 143704 KB Output is correct
12 Correct 49 ms 143720 KB Output is correct
13 Correct 47 ms 143696 KB Output is correct
14 Correct 49 ms 143636 KB Output is correct
15 Correct 46 ms 143708 KB Output is correct
16 Correct 48 ms 144720 KB Output is correct
17 Incorrect 69 ms 152400 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 142944 KB Output is correct
2 Correct 46 ms 142940 KB Output is correct
3 Correct 46 ms 142932 KB Output is correct
4 Correct 46 ms 143188 KB Output is correct
5 Correct 46 ms 142932 KB Output is correct
6 Correct 45 ms 142936 KB Output is correct
7 Correct 45 ms 142984 KB Output is correct
8 Correct 45 ms 142928 KB Output is correct
9 Correct 45 ms 143188 KB Output is correct
10 Correct 47 ms 143708 KB Output is correct
11 Correct 47 ms 143608 KB Output is correct
12 Correct 47 ms 143716 KB Output is correct
13 Correct 46 ms 143696 KB Output is correct
14 Correct 48 ms 143700 KB Output is correct
15 Correct 47 ms 143696 KB Output is correct
16 Correct 49 ms 144728 KB Output is correct
17 Incorrect 73 ms 152492 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 142940 KB Output is correct
2 Correct 46 ms 142676 KB Output is correct
3 Correct 44 ms 142940 KB Output is correct
4 Correct 45 ms 142940 KB Output is correct
5 Correct 45 ms 142928 KB Output is correct
6 Correct 47 ms 142932 KB Output is correct
7 Correct 46 ms 142940 KB Output is correct
8 Correct 45 ms 143004 KB Output is correct
9 Correct 46 ms 143260 KB Output is correct
10 Correct 46 ms 143696 KB Output is correct
11 Correct 46 ms 143700 KB Output is correct
12 Correct 47 ms 143708 KB Output is correct
13 Correct 47 ms 143700 KB Output is correct
14 Correct 47 ms 143696 KB Output is correct
15 Correct 47 ms 143704 KB Output is correct
16 Correct 50 ms 144720 KB Output is correct
17 Incorrect 73 ms 152400 KB Output isn't correct
18 Halted 0 ms 0 KB -