oj.uz

Submission #744068

# Submission time Handle Problem Language Result Execution time Memory
744068 2023-05-18T07:50:36 Z fanwen Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 51 ms 61568 KB 
#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()

#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

#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; }

const int MAXN = 2e6 + 5;
const int S = 200;
int N, M, source, sink, dp[MAXN];
vector <pair <int, int>> ke[MAXN];

void add_edges(int i, int j, int w, bool tmp = true) {
    ke[i].push_back(make_pair(j, w));
    if(tmp) ke[j].push_back(make_pair(i, w));
}

void process(void) {

    cin >> N >> M;

    auto ID = [&] (int i, int j) -> int { return (i - 1) * S + j; };

    FOR(v, 1, M) {
        int b, p; cin >> b >> p; b++;
        if(v == 1) source = b;
        if(v == 2) sink = b;
        if(p >= S) {
            for (int i = b + p; i <= N; i += p) add_edges(i, b, (i - b) / p);
            for (int i = b - p; i >= 1; i -= p) add_edges(i, b, (b - i) / p);
        } else add_edges(b, N + ID(b, p), 0, false);
    }

    FOR(i, 1, N) FOR(j, 1, S) add_edges(N + ID(i, j), i, 0, false);

    FOR(i, 1, N) FOR(j, 1, S) if(i + j <= N) {
        add_edges(N + ID(i, j), N + ID(i + j, j), 1);
    }
    memset(dp, 0x3f, sizeof dp);
    dp[source] = 0;
    priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q;
    q.push(make_pair(0, source));
    while((int) q.size()) {
        auto [w1, u] = q.top(); q.pop();
        if(dp[u] != w1) continue;
        for (auto [v, w] : ke[u]) if(minimize(dp[v], dp[u] + w)) {
            q.push(make_pair(dp[v], v));
        }
    }
    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 = 1;
    // cin >> test;
    while(test--) {
        process();
        cout << '\n';
    }
    cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(TASK ".inp", "r", stdin);  \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:69:5: note: in expansion of macro 'file'
   69 |     file("TASK");
      |     ^~~~
skyscraper.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen(TASK ".out", "w", stdout); \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:69:5: note: in expansion of macro 'file'
   69 |     file("TASK");
      |     ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 55072 KB Output is correct
2 Correct 26 ms 54988 KB Output is correct
3 Correct 27 ms 55088 KB Output is correct
4 Correct 27 ms 55088 KB Output is correct
5 Correct 27 ms 55124 KB Output is correct
6 Correct 31 ms 55088 KB Output is correct
7 Correct 28 ms 55144 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 55124 KB Output is correct
2 Correct 27 ms 55104 KB Output is correct
3 Correct 27 ms 55104 KB Output is correct
4 Correct 32 ms 55092 KB Output is correct
5 Correct 27 ms 55072 KB Output is correct
6 Correct 31 ms 55148 KB Output is correct
7 Correct 32 ms 55172 KB Output is correct
8 Correct 27 ms 55252 KB Output is correct
9 Correct 27 ms 55412 KB Output is correct
10 Correct 29 ms 55788 KB Output is correct
11 Correct 29 ms 55816 KB Output is correct
12 Correct 29 ms 55892 KB Output is correct
13 Correct 30 ms 55884 KB Output is correct
14 Correct 29 ms 55892 KB Output is correct
15 Correct 33 ms 56020 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 55116 KB Output is correct
2 Correct 28 ms 55124 KB Output is correct
3 Correct 30 ms 55136 KB Output is correct
4 Correct 27 ms 55116 KB Output is correct
5 Correct 33 ms 55124 KB Output is correct
6 Correct 28 ms 55160 KB Output is correct
7 Correct 35 ms 55124 KB Output is correct
8 Correct 29 ms 55260 KB Output is correct
9 Correct 28 ms 55480 KB Output is correct
10 Correct 30 ms 55788 KB Output is correct
11 Correct 30 ms 55764 KB Output is correct
12 Correct 30 ms 55764 KB Output is correct
13 Correct 30 ms 55756 KB Output is correct
14 Correct 29 ms 55884 KB Output is correct
15 Correct 31 ms 55848 KB Output is correct
16 Correct 31 ms 56452 KB Output is correct
17 Incorrect 50 ms 61496 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 55124 KB Output is correct
2 Correct 31 ms 55052 KB Output is correct
3 Correct 27 ms 55136 KB Output is correct
4 Correct 34 ms 55068 KB Output is correct
5 Correct 29 ms 55136 KB Output is correct
6 Correct 30 ms 55060 KB Output is correct
7 Correct 27 ms 55124 KB Output is correct
8 Correct 28 ms 55256 KB Output is correct
9 Correct 27 ms 55400 KB Output is correct
10 Correct 29 ms 55804 KB Output is correct
11 Correct 32 ms 55792 KB Output is correct
12 Correct 29 ms 55852 KB Output is correct
13 Correct 30 ms 55764 KB Output is correct
14 Correct 30 ms 55788 KB Output is correct
15 Correct 31 ms 55764 KB Output is correct
16 Correct 32 ms 56556 KB Output is correct
17 Incorrect 51 ms 61524 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 55036 KB Output is correct
2 Correct 31 ms 55056 KB Output is correct
3 Correct 30 ms 55124 KB Output is correct
4 Correct 29 ms 55056 KB Output is correct
5 Correct 29 ms 55124 KB Output is correct
6 Correct 29 ms 55144 KB Output is correct
7 Correct 30 ms 55068 KB Output is correct
8 Correct 29 ms 55328 KB Output is correct
9 Correct 30 ms 55412 KB Output is correct
10 Correct 30 ms 55764 KB Output is correct
11 Correct 32 ms 55892 KB Output is correct
12 Correct 31 ms 55752 KB Output is correct
13 Correct 31 ms 55840 KB Output is correct
14 Correct 31 ms 55844 KB Output is correct
15 Correct 30 ms 55888 KB Output is correct
16 Correct 31 ms 56524 KB Output is correct
17 Incorrect 51 ms 61568 KB Output isn't correct
18 Halted 0 ms 0 KB -