oj.uz

Submission #744045

# Submission time Handle Problem Language Result Execution time Memory
744045 2023-05-18T07:38:08 Z fanwen Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 36 ms 57588 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 = 100;
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 27 ms 55124 KB Output is correct
2 Correct 27 ms 55108 KB Output is correct
3 Correct 29 ms 55124 KB Output is correct
4 Correct 29 ms 55040 KB Output is correct
5 Correct 29 ms 55108 KB Output is correct
6 Correct 28 ms 55100 KB Output is correct
7 Correct 32 ms 55116 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55124 KB Output is correct
2 Correct 32 ms 55092 KB Output is correct
3 Correct 33 ms 55104 KB Output is correct
4 Correct 32 ms 55112 KB Output is correct
5 Correct 29 ms 55056 KB Output is correct
6 Correct 28 ms 55104 KB Output is correct
7 Correct 28 ms 55124 KB Output is correct
8 Correct 33 ms 55208 KB Output is correct
9 Correct 33 ms 55380 KB Output is correct
10 Correct 28 ms 55364 KB Output is correct
11 Correct 29 ms 55492 KB Output is correct
12 Correct 29 ms 55500 KB Output is correct
13 Correct 29 ms 55500 KB Output is correct
14 Correct 36 ms 55456 KB Output is correct
15 Correct 30 ms 55556 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 55132 KB Output is correct
2 Correct 28 ms 55124 KB Output is correct
3 Correct 27 ms 55100 KB Output is correct
4 Correct 28 ms 55128 KB Output is correct
5 Correct 27 ms 55144 KB Output is correct
6 Correct 30 ms 55124 KB Output is correct
7 Correct 28 ms 55040 KB Output is correct
8 Correct 29 ms 55220 KB Output is correct
9 Correct 29 ms 55368 KB Output is correct
10 Correct 29 ms 55452 KB Output is correct
11 Correct 32 ms 55492 KB Output is correct
12 Correct 29 ms 55496 KB Output is correct
13 Correct 30 ms 55496 KB Output is correct
14 Correct 29 ms 55524 KB Output is correct
15 Correct 32 ms 55508 KB Output is correct
16 Correct 30 ms 55764 KB Output is correct
17 Incorrect 31 ms 57588 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 55100 KB Output is correct
2 Correct 28 ms 55060 KB Output is correct
3 Correct 29 ms 55124 KB Output is correct
4 Correct 33 ms 55044 KB Output is correct
5 Correct 28 ms 55100 KB Output is correct
6 Correct 28 ms 55124 KB Output is correct
7 Correct 28 ms 55140 KB Output is correct
8 Correct 30 ms 55256 KB Output is correct
9 Correct 32 ms 55308 KB Output is correct
10 Correct 31 ms 55400 KB Output is correct
11 Correct 29 ms 55500 KB Output is correct
12 Correct 31 ms 55444 KB Output is correct
13 Correct 36 ms 55520 KB Output is correct
14 Correct 31 ms 55472 KB Output is correct
15 Correct 33 ms 55476 KB Output is correct
16 Correct 29 ms 55876 KB Output is correct
17 Incorrect 32 ms 57532 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 55048 KB Output is correct
2 Correct 28 ms 54992 KB Output is correct
3 Correct 29 ms 55104 KB Output is correct
4 Correct 33 ms 55080 KB Output is correct
5 Correct 34 ms 55132 KB Output is correct
6 Correct 28 ms 55052 KB Output is correct
7 Correct 28 ms 55104 KB Output is correct
8 Correct 29 ms 55252 KB Output is correct
9 Correct 28 ms 55352 KB Output is correct
10 Correct 28 ms 55392 KB Output is correct
11 Correct 32 ms 55572 KB Output is correct
12 Correct 29 ms 55520 KB Output is correct
13 Correct 31 ms 55472 KB Output is correct
14 Correct 34 ms 55500 KB Output is correct
15 Correct 31 ms 55508 KB Output is correct
16 Correct 30 ms 55824 KB Output is correct
17 Incorrect 33 ms 57528 KB Output isn't correct
18 Halted 0 ms 0 KB -