oj.uz

Submission #399381

# Submission time Handle Problem Language Result Execution time Memory
399381 2021-05-05T16:05:07 Z MeGustaElArroz23 Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 1 ms 296 KB 
#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;
    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 (ll i=0;i<n;i++){
        pii x=v[i];
        for (ll 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 (ll 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

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:52:27: warning: 'final' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |             if (x.second==final){
      |                           ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 272 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -