Submission #917111

#	Time	Username	Problem	Language	Result	Execution time	Memory
917111		coding_snorlax	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1088 ms	5248 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
set<pair<int,int>> s;
vector<int> List[30005];
int now_best[30005];
int vis[30005]={0};
int Move[30005];
int N,M;
int answer = 50000;
void add(){
    auto now = *(s.begin());
    vis[now.second]=1;
    s.erase(s.begin());
    for(int i:List[now.second]){
        if(i==1) answer = min(answer,now.first);
        // doge M
        for(int j=now.second;j<=N;j+=Move[i]){
            if(!vis[j]){
                int comp = now.first+(j-now.second)/Move[i];
                if(now_best[j]>comp){
                    now_best[j] = comp;
                    s.erase(make_pair(now_best[j],j));
                    s.insert(make_pair(comp,j));
                }
            }
        }
        for(int j=now.second;j>=0;j-=Move[i]){
            if(!vis[j]){
                int comp = now.first+(now.second-j)/Move[i];
                if(now_best[j]>comp){
                    now_best[j] = comp;
                    s.erase(make_pair(now_best[j],j));
                    s.insert(make_pair(comp,j));
                }
            }
        }
    }
}
int main(){
    cin>>N>>M;
    int Bos;
    for(int i=0;i<=N;i++) now_best[i]=30005;
    for(int i=0;i<M;i++){
        int tmp1,tmp2;
        cin>>tmp1>>tmp2;
        List[tmp1].push_back(i);
        Move[i]=tmp2;
        if(i==0) Bos = tmp1;
    }
    s.insert(make_pair(0,Bos));
    while((int)s.size()) add();
    if(answer!=50000) cout << answer;
    else cout << -1;

}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:50:29: warning: 'Bos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |     s.insert(make_pair(0,Bos));
      |                             ^

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