Submission #1184596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184596		inesfi	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1100 ms	56736 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
//#define int long long

const int TAILLEMAXI=30*1000+2,PMAXI=132;
int dejavu[TAILLEMAXI][PMAXI]; ///endroit,P
vector<int> depart[TAILLEMAXI];
int nbvilles,nbjumpers;
priority_queue<tuple<int,int,int>> encours; ///////// -nbcoups, pos, P

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>nbvilles>>nbjumpers;
    int posfinal;
    for (int i=0;i<nbjumpers;i++){
        int a,b;
        cin>>a>>b;
        depart[a].push_back(b);
        if (i==0){
            encours.push(make_tuple(0,a,0));
        }
        else if (i==1){
            posfinal=a;
        }
    }
    while (encours.size()!=0){
        int nbcoups=get<0>(encours.top()),pos=get<1>(encours.top()),P=get<2>(encours.top());
        //cout<<-nbcoups<<" "<<pos<<" "<<P<<endl;
        encours.pop();
        if (pos>=0 and pos<nbvilles and dejavu[pos][P]==0){
            dejavu[pos][P]=1;
            if (pos==posfinal){
                cout<<-nbcoups<<endl;
                return 0;
            }
            if (P!=0){
                if (dejavu[pos][0]==0){
                    encours.push(make_tuple(nbcoups,pos,0));
                }
                if (dejavu[pos-P][P]==0){
                    encours.push(make_tuple(nbcoups-1,pos-P,P));
                }
                if (dejavu[pos+P][P]==0){
                    encours.push(make_tuple(nbcoups-1,pos+P,P));
                }
            }
            else {
                for (int i:depart[pos]){
                    if (i<PMAXI){
                        if (dejavu[pos][i]==0){
                            encours.push(make_tuple(nbcoups,pos,i));
                        }
                    }
                    else {
                        int a=1;
                        while (pos-a*i>=0){
                            if (dejavu[pos-a*i][0]==0){
                                encours.push(make_tuple(nbcoups-a,pos-a*i,0));
                            }
                            a++;
                        }
                        a=1;
                        while (pos+a*i<nbvilles){
                            if (dejavu[pos+a*i][0]==0){
                                encours.push(make_tuple(nbcoups-a,pos+a*i,0));
                            }
                            a++;
                        }
                    }
                }
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}

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