Submission #820174

#	Time	Username	Problem	Language	Result	Execution time	Memory
820174		lprochniak	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	55 ms	34776 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define MAX 30009
#define pb push_back
#define st first
#define nd second
int n,m;
vector<int> p[MAX];
struct Node{
    int v;
    int waga;
};
vector<Node> edges[MAX];
int wyn[MAX];
void dijkstra(int s){
    priority_queue<pair<int,int>> q;
    q.push({0,s});

    while(!q.empty()){
        pair<int,int> t = q.top();
        q.pop();
        t.st = -t.st;

        for(auto x:edges[t.nd]){
            if(t.st+x.waga<wyn[x.v]){
                wyn[x.v] = t.st + x.waga;
                q.push({-wyn[x.v],x.v});
            }
        }
    }
}
int main(){
    cin>>n>>m;
    memset(p,0,sizeof p);
    int whereZero,whereOne;
    for(int i=0;i<m;i++){
        int b,pwr;
        cin>>b>>pwr;
        p[b].pb(pwr);
        if(i == 0)
            whereZero = b;
        else if(i == 1)
            whereOne = b;
    }
    for(int i=0;i<n;i++){
        if(p[i].empty()) continue;
        for(auto pwr:p[i]){
            int idx = i-pwr;
            int ile = 1;
            while(idx>=0){
                edges[i].pb({idx,ile});
                idx-=pwr,ile++;
            }
            idx = i+pwr;
            ile = 1;
            while(idx<n){
                edges[i].pb({idx,ile});
                idx+=pwr,ile++;
            }
        }
    }
    for(int i=1;i<n;i++){
        wyn[i] = 1000000000;
    }
    dijkstra(whereZero);
    
    if(wyn[whereOne] == 1000000000){
        cout<<"-1\n";
    } else
        cout<<wyn[whereOne]<<"\n";
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:34:24: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'class std::vector<int>' with no trivial copy-assignment; use assignment or value-initialization instead [-Wclass-memaccess]
   34 |     memset(p,0,sizeof p);
      |                        ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from skyscraper.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:389:11: note: 'class std::vector<int>' declared here
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
skyscraper.cpp:67:20: warning: 'whereOne' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |     if(wyn[whereOne] == 1000000000){
      |        ~~~~~~~~~~~~^
skyscraper.cpp:65:13: warning: 'whereZero' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |     dijkstra(whereZero);
      |     ~~~~~~~~^~~~~~~~~~~

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