oj.uz

Submission #250961

# Submission time Handle Problem Language Result Execution time Memory
250961 2020-07-19T16:58:46 Z eohomegrownapps Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<vector<ll>> smallpowers; //on given skyscraper
vector<vector<pair<ll,ll>>> adjlist; //weight, node

ll n;

ll INF = 1e18;

ll dijkstra(ll startloc, ll endloc){
    ll start = startloc;
    vector<vector<ll>> distances(n, vector<ll>(ll(sqrt(n))+1, INF));
    distances[start][0]=0;
    priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,less<pair<ll,pair<ll,ll>>>> pq;
    pq.push({0,{0,0}});
    while (pq.size()>0){
        auto f = pq.top();
        pq.pop();
        if (distances[f.second.first][f.second.second]<f.first){
            continue;
        }
        ll curdist = f.first;
        ll curnode = f.second.first;
        ll curind = f.second.second;
        if (curind==0){
            // we can go to a doge with cost 0
            for (ll i : smallpowers[curnode]){
                if (distances[curnode][i]>curdist){
                    distances[curnode][i]=curdist;
                    pq.push({distances[curnode][i],{curnode,i}});
                }
            }
            // or we can jump skyscrapers
            for (auto p : adjlist[curnode]){
                if (distances[p.second][0]>curdist+p.first){
                    distances[p.second][0]=curdist+p.first;
                    pq.push({distances[p.second][0],{p.second,0}});
                }
            }
        } else {
            //we can go to central node with cost 0
            if (distances[curnode][0]>curdist){
                distances[curnode][0]=curdist;
                pq.push({distances[curnode][0],{curnode,0}});
            }
            //or we can go to an adjacent node
            if (curnode-curind>=0&&distances[curnode-curind][curind]>curdist+1){
                distances[curnode-curind][curind]=curdist+1;
                pq.push({distances[curnode-curind][curind],{curnode-curind,curind}});
            }
            if (curnode+curind<n&&distances[curnode+curind][curind]>curdist+1){
                distances[curnode+curind][curind]=curdist+1;
                pq.push({distances[curnode+curind][curind],{curnode+curind,curind}});
            }
        }
    }
    return distances[endloc][0];
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    ll m;
    cin>>n>>m;
    ll sqrtv = sqrt(n);
    smallpowers.resize(n);
    adjlist.resize(n);
    ll startloc = 0;
    ll endloc = 0;
    for (ll i = 0; i<m; i++){
        ll b,p;
        cin>>b>>p;
        if (i==0){
            startloc=b;
        } 
        if (i==1){
            endloc=b;
        }
        //skyscraper b, moves p
        if (p<sqrtv){
            smallpowers[b].push_back(p);
        } else {
            ll cnt = 0;
            for (ll x = b+p; x<n; x+=p){
                cnt++;
                adjlist[b].push_back({cnt,x});
            } 
            cnt = 0;
            for (ll x = b-p; x>=0; x-=p){
                cnt++;
                adjlist[b].push_back({cnt,x});
            }
        }
    }
    ll d = dijkstra(startloc,endloc);
    if (d==INF){
        cout<<-1<<'\n';
    } else {
        cout<<d<<'\n';
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -