Submission #399369

#	Time	Username	Problem	Language	Result	Execution time	Memory
399369		MeGustaElArroz23	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1087 ms	81176 KiB

skyscraper

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

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;

int main(){
    ll l,n;
    cin >> l >> n;
    vii v(n);
    for (ll i=0;i<n;i++) cin >> v[i].first >> v[i].second;
    vvii conexiones(n);
    
    for (ll i=0;i<n;i++){
        pii x=v[i];
        for (ll j=0;j<n;j++){
            pii y=v[j];
            if (i==j) continue;
            if (y.first%x.second==x.first%x.second) conexiones[i].push_back(pii{abs(x.first-y.first)/x.second,j});
        }
    }
    priority_queue<pii> cola;
    cola.push(pii{0,0});
    bool T=true;
    vi porvisitar(n,true);
    //for (int i=0;i<n;i++){
    //    for (pii x:conexiones[i]) cerr << x.second<<x.first<<' ';
    //    cerr<<'\n';
    //}
    while (cola.size()){
        pii x=cola.top();
        cola.pop();
        if (porvisitar[x.second]){
            porvisitar[x.second]=false;
            if (x.second==1){
                T=false;
                cout << -x.first << '\n';
                break;
            }
            for (pii y:conexiones[x.second]){
                if (porvisitar[y.second]) cola.push(pii{x.first-y.first,y.second});
            }
        }
    }
    if (T) cout << -1<<'\n';
}

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