oj.uz

Submission #946445

# Submission time Handle Problem Language Result Execution time Memory
946445 2024-03-14T16:35:10 Z raul2008487 Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 1 ms 1116 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;
bool used[sz];
vl pos[sz];
void solve(){
    ll n, m, i, j, c;
    cin >> n >> m;
    map<pair<ll, ll>, ll> mp;
    vl b(m + 1), p(m + 1);
    for(i = 1; i <= m; i++){
        cin >> b[i] >> p[i];
        b[i]++;
        if(mp[mpr(b[i], p[i])]){continue;}
        mp[mpr(b[i], p[i])]++;
        pos[b[i]].pb(p[i]);
    }
    priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
    pq.push({0, b[1]});
    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 == b[2]){
            cout << dtov << endl;
            return ;
        }
        if(used[v]){continue;}
        used[v] = 1;
        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:21:17: warning: unused variable 'j' [-Wunused-variable]
   21 |     ll n, m, i, j, c;
      |                 ^

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Incorrect 1 ms 1116 KB Output isn't correct
9 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 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Incorrect 1 ms 1116 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

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

Subtask #5
0 / 43.0

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