Submission #27365

#	Time	Username	Problem	Language	Result	Execution time	Memory
27365		TAMREF	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	449 ms	9480 KiB

skyscraper

#include <bits/stdc++.h>
#define va first
#define vb second
#define mp make_pair
#define all(x) x.begin(),x.end()
using namespace std;
typedef pair<int,int> pii;
const int mx=30005;
int dist[mx], B[mx], P[mx];
vector<int> C[mx];
int N,M;
void input(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        scanf("%d%d",&B[i],&P[i]);
        C[B[i]].push_back(P[i]);
    }
    for(int i=0;i<N;i++){
        sort(all(C[i]));
        C[i].erase(unique(all(C[i])),C[i].end());
    }
    fill(dist,dist+N,(int)1e9);
}
void dijk(int s){
    priority_queue<pii,vector<pii>,greater<pii>> q;
    q.push(mp(dist[s]=0,s));
    pii t;
    while(!q.empty()){
        t=q.top(); q.pop();
        if(t.va>dist[t.vb]) continue;
        for(int p : C[t.vb]){
            for(int x=1;t.vb+p*x<N;++x){
                if(dist[t.vb+p*x]>t.va+x){
                    q.push(mp(dist[t.vb+p*x]=t.va+x,t.vb+p*x));
                    if(binary_search(all(C[t.vb+p*x]),p)) break;
                }
            }
            for(int x=1;t.vb-p*x>=0;++x){
                if(dist[t.vb-p*x]>t.va+x){
                    q.push(mp(dist[t.vb-p*x]=t.va+x,t.vb-p*x));
                    if(binary_search(all(C[t.vb-p*x]),p)) break;
                }
            }
        }
    }
}
int main(){
    input();
    dijk(B[0]);
    printf("%d\n",dist[B[1]]==(int)1e9?-1:dist[B[1]]);
}

Compilation message (stderr)

skyscraper.cpp: In function 'void input()':
skyscraper.cpp:13:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&N,&M);
                        ^
skyscraper.cpp:15:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&B[i],&P[i]);
                                  ^

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