Submission #1184549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184549		inesfi	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	53 ms	24388 KiB

skyscraper

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

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

const int TAILLEMAXI=2002;
int dejavu[TAILLEMAXI][TAILLEMAXI]; ///endroit,P
vector<int> depart[TAILLEMAXI];
int nbvilles,nbjumpers;
vector<pair<int,int>> jumpers; /////endroit,P
deque<pair<int,int>> encours;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>nbvilles>>nbjumpers;
    for (int i=0;i<nbjumpers;i++){
        int a,b;
        cin>>a>>b;
        jumpers.push_back({a,b});
        depart[a].push_back(b);
    }
    encours.push_back({jumpers[0].first,jumpers[0].second});
    int posfinal=jumpers[1].first;
    int rep=0;
    while (encours.size()!=0){
        int taille=encours.size();
        int a=0;
        while (a<taille){
            int pos=encours.front().first,saut=encours.front().second;
            encours.pop_front();
            a++;
            if (pos>=0 and pos<nbvilles and dejavu[pos][saut]==0){
                dejavu[pos][saut]=1;
                if (pos==posfinal){
                    cout<<rep<<endl;
                    return 0;
                }
                for (int i:depart[pos]){
                    if (i!=saut){
                        encours.push_front({pos,i});
                        a--;
                    }
                }
                encours.push_back({pos-saut,saut});
                encours.push_back({pos+saut,saut});
            }
        }
        rep++;
        /*cout<<encours[0].first<<" "<<encours[0].second<<endl;
        cout<<encours[1].first<<" "<<encours[1].second<<endl;
        return 0;*/
    }
    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