Submission #823582

#	Time	Username	Problem	Language	Result	Execution time	Memory
823582		lprochniak	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	382 ms	262144 KiB

skyscraper

//https://oj.uz/problem/view/APIO15_skyscraper
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
#define pii pair<int,int>
int n,m;
int root;
//position / power
struct E{
    int pos;
    int pow;
    int waga;
};
struct Node{
    int d;
    int pos;
    int pow;
};
class comp{
    public:
        bool operator()(Node A,Node B){
            return A.d<B.d;
        }
};
map<pair<int,int>,bool> odw;
vector<E> edges[30009][174];
int dis[30009][174];
void build(){
    for(int i=0;i<n;i++){
        for(int j=1;j<=root;j++){
            edges[i][j].pb({i,0,0});
        }
    }
}
void addsmaller(int pos,int pow){
    int pos2 = pos;
    while(pos2+pow<n){
        edges[pos2][pow].pb({pos2+pow,pow,1});
        pos2 += pow;
    }
    pos2 = pos;
    while(pos2-pow>=0){
        edges[pos2][pow].pb({pos2-pow,pow,1});
        pos2 -= pow;
    }
}
void addbigger(int pos,int pow){
    int pos2 = pos;
    int dl = 1;
    while(pos2+pow<n){
        edges[pos][0].pb({pos2+pow,0,dl});
        pos2 += pow;
        dl++;
    }
    pos2 = pos;
    dl = 1;
    while(pos2-pow>=0){
        edges[pos][0].pb({pos2-pow,0,dl});
        pos2 -= pow;
        dl++;
    }
}
void dijkstra(int pocz){
    priority_queue<Node,vector<Node>,comp> q;
    q.push({0,pocz,0});
    while(!q.empty()){
        auto t = q.top();
        q.pop();
        t.d = -t.d;
        if(dis[t.pos][t.pow] != t.d)
            continue;
        for(auto x:edges[t.pos][t.pow]){
            if(t.d + x.waga < dis[x.pos][x.pow]){
                dis[x.pos][x.pow] = t.d + x.waga;
                q.push({-dis[x.pos][x.pow],x.pos,x.pow});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    root = (int)sqrt(n);
    build();
    int zero,one;
    for(int i=0;i<m;i++){
        int pos,pow;
        cin>>pos>>pow;
		  pii para = {pos,pow};
        if(odw[{pos,pow}]) continue;
            else odw[{pos,pow}] = 1;
        if(pow <= root){
            edges[pos][0].pb({pos,pow,0});
            addsmaller(pos,pow);
        } else if(pow<=n){
            addbigger(pos,pow);
        }
        if(i>1) continue;

        if(i == 0){
            zero = pos;
        } else if(i == 1){
            one = pos;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=root;j++){
            dis[i][j] = 1000000000;
        }
    }
    dis[zero][0] = 0;
    dijkstra(zero);
    /*
    for(int i=0;i<n;i++){
        for(int j=0;j<=n;j++){
            cout<<"pos: "<<i<<" pow: "<<j<<endl;
            s += edges[i][j].size();
            for(auto x:edges[i][j]){
                cout<<"pos: "<<x.pos<<" pow: "<<x.pow<<" waga: "<<x.waga<<endl;
            }
        }
    }*/
    if(dis[one][0] == 1000000000){
        cout<<"-1\n";
    } else cout<<dis[one][0]<<endl;
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:91:9: warning: variable 'para' set but not used [-Wunused-but-set-variable]
   91 |     pii para = {pos,pow};
      |         ^~~~
skyscraper.cpp:125:18: warning: 'one' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |     if(dis[one][0] == 1000000000){
      |        ~~~~~~~~~~^
skyscraper.cpp:114:13: warning: 'zero' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |     dijkstra(zero);
      |     ~~~~~~~~^~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43