Submission #744014

#	Time	Username	Problem	Language	Result	Execution time	Memory
744014		fanwen	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	460 ms	154348 KiB

skyscraper

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

#define MASK(x) (1LL << (x))
#define BIT(x, k) (((x) >> (k)) & 1LL)
#define ALL(x) (x).begin(),(x).end()
#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define Fod(i, a, b) for (int i = (a); i >= (b); --i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define Fore(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }

template <class U, class V> bool maximize(U &A, const V &B){ return (A < B) ? (A = B, true) : false;}
template <class U, class V> bool minimize(U &A, const V &B){ return (A > B) ? (A = B, true) : false;}

using namespace std;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) { return l + rnd() % (r - l + 1); }
const int MAXN = 2e6 + 5;
int N, M, source, sink;
vector <pair <int, int>> ke[MAXN];
int dp[MAXN];
int ID(int x, int y) {
    return (x - 1) * 30 + y;
}
void solve(void) {
    cin >> N >> M;
    For (i, 1, M) {
        int b, q; cin >> b >> q; b++;
        if(i == 1) source = b;
        if(i == 2) sink = b;
        if(q >= 30) {
            for (int j = b - q; j >= 1; j -= q) ke[b].push_back(make_pair(j, (b - j) / q));
            for (int j = b + q; j <= N; j += q) ke[b].push_back(make_pair(j, (j - b) / q));
        } else ke[b].push_back(make_pair(N + ID(b, q), 0));
    }
    For (i, 1, N) For (j, 1, 30) {
        ke[N + ID(i, j)].push_back(make_pair(i, 0));
    }
    For (i, 1, N) For (j, 1, 30) if(i + j <= N) {
        ke[N + ID(i, j)].push_back(make_pair(N + ID(i + j, j), 1));
        ke[N + ID(i + j, j)].push_back(make_pair(N + ID(i, j), 1));
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[source] = 0;
    priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;
    heap.push(make_pair(0, source));
    while(heap.size()) {
        int u = heap.top().second; heap.pop();
        for (auto v : ke[u]) if(minimize(dp[v.first], dp[u] + v.second)) {
            heap.push(make_pair(dp[v.first], v.first));
        }
    }
    cout << (dp[sink] >= 1e9 ? -1 : dp[sink]);
}
signed main() {
    file("TASK");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int test; test = 1;
    // cin >> test;
    while(test--){
        solve();
        cout << '\n';
    }
    // cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:14:56: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
      |                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:61:5: note: in expansion of macro 'file'
   61 |     file("TASK");
      |     ^~~~
skyscraper.cpp:14:89: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
      |                                                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:61:5: note: in expansion of macro 'file'
   61 |     file("TASK");
      |     ^~~~

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