oj.uz

Submission #250967

# Submission time Handle Problem Language Result Execution time Memory
250967 2020-07-19T17:05:25 Z eohomegrownapps Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 4 ms 1792 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> smallpowers[30000]; //on given skyscraper
vector<pair<int,int>> adjlist[30000]; //weight, node

int n;

int INF = 1e9;
int distances[30000][175];

int dijkstra(int startloc, int endloc){
    int start = startloc;
    for (int i = 0; i<n; i++){
        for (int j = 0; j<int(sqrt(n))+1; j++){
            distances[i][j]=INF;
        }
    }
    distances[start][0]=0;
    priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,less<pair<int,pair<int,int>>>> pq;
    pq.push({0,{start,0}});
    while (pq.size()>0){
        auto f = pq.top();
        pq.pop();
        if (distances[f.second.first][f.second.second]<f.first){
            continue;
        }
        int curdist = f.first;
        int curnode = f.second.first;
        int curind = f.second.second;
        if (curind==0){
            // we can go to a doge with cost 0
            for (int 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);
    int m;
    cin>>n>>m;
    int sqrtv = sqrt(max(n,m));
    //smallpowers.resize(n);
    //adjlist.resize(n);
    int startloc = 0;
    int endloc = 0;
    for (int i = 0; i<m; i++){
        int 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 {
            int cnt = 0;
            for (int x = b+p; x<n; x+=p){
                cnt++;
                adjlist[b].push_back({cnt,x});
            } 
            cnt = 0;
            for (int x = b-p; x>=0; x-=p){
                cnt++;
                adjlist[b].push_back({cnt,x});
            }
        }
    }
    int 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 1 ms 1792 KB Output is correct
2 Correct 2 ms 1792 KB Output is correct
3 Correct 2 ms 1792 KB Output is correct
4 Correct 1 ms 1792 KB Output is correct
5 Correct 1 ms 1792 KB Output is correct
6 Correct 1 ms 1792 KB Output is correct
7 Correct 1 ms 1792 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 43.0

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