Submission #823612

#	Time	Username	Problem	Language	Result	Execution time	Memory
823612		lprochniak	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	330 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>
#define int short
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;
        }
};
vector<pair<int,int>> kand,doges;
bool odw[174][175];
vector<E> edges[30001][175];
int dis[30001][175];
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){
    if(odw[pow][pos%pow]) return;
        else odw[pow][pos%pow] = 1;
    int pos2 = pos;
    while(pos2+pow<n){
        edges[pos2][pow].pb({pos2+pow,pow,1});
        edges[pos2+pow][pow].pb({pos2,pow,1});
        pos2 += pow;
    }
    pos2 = pos;
    while(pos2-pow>=0){
        edges[pos2][pow].pb({pos2-pow,pow,1});
        edges[pos2-pow][pow].pb({pos2,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++;
    }
}
priority_queue<Node,vector<Node>,comp> q;
void dijkstra(int pocz){
    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});
            }
        }
    }
}
__int32_t 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;
        kand.pb({pos,pow});
        if(i>1) continue;
        if(i == 0){
            zero = pos;
        } else if(i == 1){
            one = pos;
        }
    }
    sort(kand.begin(),kand.end());
    doges.pb(kand[0]);
    for(int i=1;i<m;i++){
        if(kand[i-1] != kand[i])
            doges.pb(kand[i]);
    }
    memset(odw,0,sizeof odw);
    for(int i=0;i<doges.size();i++){
        int pos = doges[i].st;
        int pow = doges[i].nd;
        if(pow <= root){
            edges[pos][0].pb({pos,pow,0});
            addsmaller(pos,pow);
        } else if(pow<=n){
            addbigger(pos,pow);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=root;j++){
            dis[i][j] = SHRT_MAX-1;
        }
    }
    dis[zero][0] = 0;
    dijkstra(zero);
    /*
    pair<long long,pii> maxi = {0,{0,0}};
    int s = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=root;j++){
            s += edges[i][j].size();
            if(edges[i][j].size()>maxi.st)
                maxi = {(long long)edges[i][j].size(),{i,j}};
            //cout<<"pos: "<<i<<" pow: "<<j<<endl;
            //for(auto x:edges[i][j]){
                //cout<<"pos: "<<x.pos<<" pow: "<<x.pow<<" waga: "<<x.waga<<endl;
            //}
        }
    }
    cout<<s<<" "<<maxi.st<<" "<<maxi.nd.st<<" "<<maxi.nd.nd<<endl;
    */
    if(dis[one][0] == SHRT_MAX-1){
        cout<<"-1\n";
    } else cout<<dis[one][0]<<endl;
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void addsmaller(short int, short int)':
skyscraper.cpp:44:34: warning: narrowing conversion of '(((int)pos2) + ((int)pow))' from 'int' to 'short int' [-Wnarrowing]
   44 |         edges[pos2][pow].pb({pos2+pow,pow,1});
      |                              ~~~~^~~~
skyscraper.cpp:50:34: warning: narrowing conversion of '(((int)pos2) - ((int)pow))' from 'int' to 'short int' [-Wnarrowing]
   50 |         edges[pos2][pow].pb({pos2-pow,pow,1});
      |                              ~~~~^~~~
skyscraper.cpp: In function 'void addbigger(short int, short int)':
skyscraper.cpp:59:31: warning: narrowing conversion of '(((int)pos2) + ((int)pow))' from 'int' to 'short int' [-Wnarrowing]
   59 |         edges[pos][0].pb({pos2+pow,0,dl});
      |                           ~~~~^~~~
skyscraper.cpp:66:31: warning: narrowing conversion of '(((int)pos2) - ((int)pow))' from 'int' to 'short int' [-Wnarrowing]
   66 |         edges[pos][0].pb({pos2-pow,0,dl});
      |                           ~~~~^~~~
skyscraper.cpp: In function 'void dijkstra(short int)':
skyscraper.cpp:83:25: warning: narrowing conversion of '-(int)dis[((int)x.E::pos)][((int)x.E::pow)]' from 'int' to 'short int' [-Wnarrowing]
   83 |                 q.push({-dis[x.pos][x.pow],x.pos,x.pow});
      |                         ^~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function '__int32_t main()':
skyscraper.cpp:112:18: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<std::pair<short int, short int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i=0;i<doges.size();i++){
      |                 ~^~~~~~~~~~~~~
skyscraper.cpp:145:12: warning: 'one' may be used uninitialized in this function [-Wmaybe-uninitialized]
  145 |     if(dis[one][0] == SHRT_MAX-1){
      |            ^~~
skyscraper.cpp:127:9: warning: 'zero' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |     dis[zero][0] = 0;
      |         ^~~~

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