Submission #74723

#	Time	Username	Problem	Language	Result	Execution time	Memory
74723		goodbaton	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	109 ms	40520 KiB

skyscraper

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;

typedef long long ll;
#define SIZE 30000
#define INF 2000000000


int N,M,B[SIZE],P[SIZE],s,g,cost[SIZE];
vector<int> way[SIZE];
bool kaku[SIZE];
bool wayn[SIZE][1001];

int main(){
    
    scanf("%d%d",&N,&M);
    
    for(int i=0;i<N;i++){
        cost[i]=-INF;
    }
    
    for(int i=0;i<M;i++){
        scanf("%d%d",&B[i],&P[i]);
        
        if(i==0){
            s = B[i];
        }
        
        if(i==1){
            g = B[i];
        }
        
        if(P[i]<=1000)
            if(wayn[B[i]][P[i]])
                continue;
        
        way[B[i]].push_back(i);
        
        if(P[i]<=1000)
            wayn[B[i]][P[i]]=true;
    }
    
    priority_queue<pair<int,int> > pq;
    
    pq.push(make_pair(0,s));
    
    while(!pq.empty()){
        pair<int,int> p=pq.top();
        pq.pop();
        
        int now = p.second;
        
        if(now==g){
            printf("%d\n",-p.first);
            return 0;
        }
        
        if(kaku[now]) continue;
        kaku[now]=true;
        
        for(int i=way[now].size()-1;i>=0;i--){
            int doge = way[now][i];
            
            for(int j=1;B[doge]+j*P[doge]<N;j++){
                
                if(cost[now+j*P[doge]]<p.first-j){
                    pq.push(make_pair(p.first-j,now+j*P[doge]));
                    cost[now+j*P[doge]]=p.first-j;
                }
                
                if(P[doge]<=1000)
                    if(wayn[now+j*P[doge]][P[doge]]) break;
            }
            
            for(int j=1;B[doge]-j*P[doge]>=0;j++){
                if(cost[now-j*P[doge]]<p.first-j){
                    pq.push(make_pair(p.first-j,now-j*P[doge]));
                    cost[now-j*P[doge]]=p.first-j;
                }
                
                if(P[doge]<=1000)
                    if(wayn[now-j*P[doge]][P[doge]]) break;
            }
        }
    }
    
    
    printf("-1\n");

    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&N,&M);
     ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:32:14: 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