Submission #298644

#	Time	Username	Problem	Language	Result	Execution time	Memory
298644		errorgorn	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	102 ms	7036 KiB

skyscraper

#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;
typedef pair<int,int> ii;

const int SQRTN=300;
const int MAXN=30005;

int n,k;
int w[MAXN];
bool pow[SQRTN][MAXN];
vector<int> power[MAXN];
priority_queue<ii,vector<ii>,greater<ii> > pq;


int main(){
    scanf("%d%d",&n,&k);
    
    int a,b;
    int s,t;
    for (int x=0;x<k;x++){
        scanf("%d%d",&a,&b);
        
        if (x==0) s=a;
        else if (x==1) t=a;
        if (b<SQRTN){
            if (pow[b][a]) continue;
            pow[b][a]=true;
            power[a].push_back(b);
        }
        else{
            power[a].push_back(b);
        }
    }
    
    memset(w,127,sizeof(w));
    w[s]=0;
    pq.push(ii(w[s],s));
    
    int node,weight;
    while (!pq.empty()){
        node=pq.top().second,weight=pq.top().first,pq.pop();
        //printf("%d %d\n",node,weight);
        
        if (w[node]!=weight) continue;
        if (node==t){
            printf("%d\n",weight);
            return 0;
        }
        
        for (auto &p:power[node]){
            for (int x=node-p;x>=0;x-=p){
                if (w[x]>weight+(node-x)/p){
                    w[x]=weight+(node-x)/p;
                    pq.push(ii(w[x],x));
                }
                if (p<SQRTN && pow[p][x]) break;
            }
            for (int x=node+p;x<MAXN;x+=p){
                if (w[x]>weight+(x-node)/p){
                    w[x]=weight+(x-node)/p;
                    pq.push(ii(w[x],x));
                }
                if (p<SQRTN && pow[p][x]) break;
            }
        }
    }
    
    printf("-1\n");
}

Compilation message (stderr)

skyscraper.cpp:13:6: warning: built-in function 'pow' declared as non-function [-Wbuiltin-declaration-mismatch]
   13 | bool pow[SQRTN][MAXN];
      |      ^~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:22:9: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   22 |     int s,t;
      |         ^
skyscraper.cpp:48:9: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |         if (node==t){
      |         ^~

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