Submission #399402

#	Time	Username	Problem	Language	Result	Execution time	Memory
399402		MeGustaElArroz23	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1090 ms	7804 KiB

skyscraper

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

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

int main(){
    int l,n;
    cin >> l >> n;
    vii v(n);
    int a=1,b=0;
    //for (int i=0;i<n;i++){
    //    if (b<a) v[i]=pii{a*(a-1)/2+b,a};
    //    else{b=0;a++;};
    //}
    //v[1]=pii{n-1,n-1};
    for (int i=0;i<n;i++) cin >> v[i].first >> v[i].second;
    pii in=v[0];
    pii fin=v[1];
    sort(v.begin(),v.end());
    int inicio,final;
    for (int i=0;i<n;i++){
        if (v[i]==in) inicio=i;
        if (v[i]==fin) final=i;
    }
    
    vvii conexiones(n);
    
    for (int i=0;i<n;i++){
        pii x=v[i];
        for (int j=i-1;j>=0;j--){
            pii y=v[j];
            if (y.first%x.second==x.first%x.second){
                conexiones[i].push_back(pii{abs(x.first-y.first)/x.second,j});
                if (x.second==y.second) break;
            }
        }
        
        for (int j=i+1;j<n;j++){
            pii y=v[j];
            
            if (y.first%x.second==x.first%x.second){
                
                conexiones[i].push_back(pii{abs(x.first-y.first)/x.second,j});
                
                if (x.second==y.second) break;
            }
            
        }
        
    }
    priority_queue<pii> cola;
    cola.push(pii{0,inicio});
    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==final){
                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';
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:14:9: warning: unused variable 'a' [-Wunused-variable]
   14 |     int a=1,b=0;
      |         ^
skyscraper.cpp:14:13: warning: unused variable 'b' [-Wunused-variable]
   14 |     int a=1,b=0;
      |             ^
skyscraper.cpp:69:13: warning: 'final' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |             if (x.second==final){
      |             ^~

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