oj.uz

Submission #744060

# Submission time Handle Problem Language Result Execution time Memory
744060 2023-05-18T07:45:18 Z fanwen Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 41 ms 59980 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 - i) {
        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 55124 KB Output is correct
2 Correct 27 ms 55088 KB Output is correct
3 Correct 28 ms 55184 KB Output is correct
4 Correct 25 ms 55124 KB Output is correct
5 Correct 25 ms 55124 KB Output is correct
6 Correct 25 ms 55124 KB Output is correct
7 Correct 26 ms 55168 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 55128 KB Output is correct
2 Correct 25 ms 55108 KB Output is correct
3 Correct 27 ms 55160 KB Output is correct
4 Correct 30 ms 55120 KB Output is correct
5 Correct 26 ms 55124 KB Output is correct
6 Correct 26 ms 55216 KB Output is correct
7 Correct 28 ms 55168 KB Output is correct
8 Correct 30 ms 55508 KB Output is correct
9 Correct 28 ms 55764 KB Output is correct
10 Correct 29 ms 56076 KB Output is correct
11 Correct 30 ms 56148 KB Output is correct
12 Correct 29 ms 56120 KB Output is correct
13 Correct 29 ms 56132 KB Output is correct
14 Correct 30 ms 56060 KB Output is correct
15 Correct 35 ms 56172 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 55124 KB Output is correct
2 Correct 26 ms 55124 KB Output is correct
3 Correct 26 ms 55124 KB Output is correct
4 Correct 27 ms 55200 KB Output is correct
5 Correct 26 ms 55176 KB Output is correct
6 Correct 29 ms 55124 KB Output is correct
7 Correct 30 ms 55180 KB Output is correct
8 Correct 29 ms 55508 KB Output is correct
9 Correct 38 ms 55688 KB Output is correct
10 Correct 32 ms 56148 KB Output is correct
11 Correct 31 ms 56136 KB Output is correct
12 Correct 30 ms 56032 KB Output is correct
13 Correct 28 ms 56120 KB Output is correct
14 Correct 28 ms 56112 KB Output is correct
15 Correct 28 ms 56204 KB Output is correct
16 Correct 30 ms 56464 KB Output is correct
17 Incorrect 35 ms 59964 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 55136 KB Output is correct
2 Correct 26 ms 55064 KB Output is correct
3 Correct 28 ms 55132 KB Output is correct
4 Correct 27 ms 55156 KB Output is correct
5 Correct 27 ms 55152 KB Output is correct
6 Correct 27 ms 55124 KB Output is correct
7 Correct 27 ms 55164 KB Output is correct
8 Correct 29 ms 55436 KB Output is correct
9 Correct 28 ms 55764 KB Output is correct
10 Correct 35 ms 56120 KB Output is correct
11 Correct 35 ms 56096 KB Output is correct
12 Correct 31 ms 56136 KB Output is correct
13 Correct 31 ms 56120 KB Output is correct
14 Correct 31 ms 56088 KB Output is correct
15 Correct 33 ms 56112 KB Output is correct
16 Correct 32 ms 56512 KB Output is correct
17 Incorrect 41 ms 59980 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 55060 KB Output is correct
2 Correct 27 ms 54988 KB Output is correct
3 Correct 32 ms 55124 KB Output is correct
4 Correct 27 ms 55124 KB Output is correct
5 Correct 28 ms 55172 KB Output is correct
6 Correct 26 ms 55168 KB Output is correct
7 Correct 28 ms 55132 KB Output is correct
8 Correct 31 ms 55500 KB Output is correct
9 Correct 27 ms 55772 KB Output is correct
10 Correct 30 ms 56096 KB Output is correct
11 Correct 30 ms 56140 KB Output is correct
12 Correct 32 ms 56140 KB Output is correct
13 Correct 29 ms 56072 KB Output is correct
14 Correct 30 ms 56116 KB Output is correct
15 Correct 30 ms 56148 KB Output is correct
16 Correct 29 ms 56532 KB Output is correct
17 Incorrect 35 ms 59888 KB Output isn't correct
18 Halted 0 ms 0 KB -