oj.uz

Submission #946433

# Submission time Handle Problem Language Result Execution time Memory
946433 2024-03-14T16:27:42 Z raul2008487 Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 1 ms 1368 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define vl vector<ll>
#define fi firp
#define se second
#define in insert
#define mpr make_pair
#define lg(x) __lg(x)
#define bpc(x) __builtin_popcount(x)
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int sz = 3e4+5;
const ll inf = 100000000000000000;
const ll LG = 26;
vl pos[sz];
void solve(){
    ll n, m, i, j, b, p, c;
    cin >> n >> m;
    map<pair<ll, ll>, ll> mp;
    for(i = 1; i <= m; i++){
        cin >> b >> p;
        if(mp[mpr(b, p)]){continue;}
        mp[mpr(b, p)]++;
        pos[b + 1].pb(p);
    }
    priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
    pq.push({0ll, 1ll});
    vl dis(n + 1, inf);
    dis[1] = 0;
    while(!pq.empty()){
        ll v = pq.top()[1];
        ll dtov = pq.top()[0];
        pq.pop();
        if(v == 2){
            cout << dtov << endl;
            return ;
        }
        if(dtov != dis[v]){continue;}
        for(auto P: pos[v]){
            c = 1;
            for(i = v + P; i <= n; i += P, c++){
                if(dis[i] > dis[v] + c){
                    dis[i] = dis[v] + c;
                    pq.push({dis[i], i});
                }
            }
            c = 1;
            for(i = v - P; i > 0; i -= P, c++){
                if(dis[i] > dis[v] + c){
                    dis[i] = dis[v] + c;
                    pq.push({dis[i], i});
                }
            }
        }
    }
    cout << -1 << endl;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    ///cin >> t;
    while(t--){
        solve();
    }
}

Compilation message

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:20:17: warning: unused variable 'j' [-Wunused-variable]
   20 |     ll n, m, i, j, b, p, c;
      |                 ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Incorrect 1 ms 1116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Incorrect 1 ms 1116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Incorrect 1 ms 1116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Incorrect 1 ms 1112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Incorrect 1 ms 1112 KB Output isn't correct
3 Halted 0 ms 0 KB -