Submission #516212

#	Time	Username	Problem	Language	Result	Execution time	Memory
516212		Dirii	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	749 ms	46396 KiB

skyscraper

// #pragma GCC target("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define cll const ll
#define lp(a, b, c) for(ll a = b; a <= c; ++a)
#define lpd(a, b, c) for(ll a = b; a >= c; --a)
#define vec(a) vector<a>
#define pp(a, b) pair<a, b>
#define EACHCASE lpd(cs, read(), 1)
#define Fname "f"
using namespace std;

template <typename T> inline void Read(T &x){
    x = 0; char c;
    ll dau = 1;
    while(!isdigit(c = getchar())) if(c == '-') dau = -1;
    do{
        x = x * 10 + c - '0';
    } while (isdigit(c = getchar()));
    x *= dau;
}

ll read(){
    ll tmp;
    cin >> tmp;
    return tmp;
}

void giuncute(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}

void OF(){
    if(fopen(Fname".inp", "r")){
        freopen(Fname".inp", "r", stdin);
        freopen(Fname".out", "w", stdout);
    } else if(fopen(Fname".in", "r")){
        freopen(Fname".in", "r", stdin);
        freopen(Fname".out", "w", stdout);
    }
}

cll mxn = 3e4 + 5, _sqrt = 173;
ll n, m, dp[mxn][_sqrt + 4], initu, initp, finalu, finalp;
vec(ll) jump[mxn];
priority_queue<pp(ll, pp(ll, ll))> q;
bool visited[mxn] = {0};

void prc(ll u, ll cu, ll step){
    if(u + step < n && dp[u + step][step] > cu + 1){
        dp[u + step][step] = cu + 1;
        q.push({-dp[u + step][step], {u + step, step}});
    } 
    if(u - step >= 0 && dp[u - step][step] > cu + 1){
        dp[u - step][step] = cu + 1;
        q.push({-dp[u - step][step], {u - step, step}});
    } 
}

int main(){
    giuncute();
    #ifndef ONLINE_JUDGE
    OF();
    #endif
    cin >> n >> m;
    lp(i, 1, m){
        static ll u, p;
        cin >> u >> p;
        if(i == 1) initu = u, initp = p;
        if(i == 2) finalu = u, finalp = p;
        jump[u].push_back(p);
    }
    lp(i, 0, n) lp(j, 0, _sqrt) dp[i][j] = 1e16;
    dp[initu][0] = 0;
    q.push({0, {initu, 0}});
    ll ans = 1e16;
    while(q.size()){
        ll cu = -q.top().first, u = q.top().second.first, step = q.top().second.second;
        q.pop();
        if(cu != dp[u][step]) continue;
        if(u == finalu) ans = min(ans, cu);

        // maintain last step
        prc(u, cu, step);

        if(visited[u]) continue;
        visited[u] = 1;
        // change step
        for(ll i : jump[u]){
            if(i <= _sqrt)
                prc(u, cu, i);
            else{
                for(ll v = u + i, cnt = 1; v < n; v += i, ++cnt)
                    if(dp[v][0] > cu + cnt){
                        dp[v][0] = cu + cnt;
                        q.push({-dp[v][0], {v, 0}});
                    }
                for(ll v = u - i, cnt = 1; v >= 0; v -= i, ++cnt)
                    if(dp[v][0] > cu + cnt){
                        dp[v][0] = cu + cnt;
                        q.push({-dp[v][0], {v, 0}});
                    }
            }
        }
    }
    if(ans > 1e15) ans = -1;
    cout << ans;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void OF()':
skyscraper.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(Fname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(Fname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(Fname".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(Fname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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