oj.uz

Submission #744082

# Submission time Handle Problem Language Result Execution time Memory
744082 2023-05-18T07:54:31 Z fanwen Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
 440 ms 154552 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 = 30;
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(b, i, (i - b) / p, false);
            for (int i = b - p; i >= 1; i -= p) add_edges(b, i, (b - i) / p, false);
        } 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 30 ms 55124 KB Output is correct
2 Correct 29 ms 55008 KB Output is correct
3 Correct 30 ms 55048 KB Output is correct
4 Correct 29 ms 55136 KB Output is correct
5 Correct 33 ms 55056 KB Output is correct
6 Correct 29 ms 54996 KB Output is correct
7 Correct 29 ms 55072 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55040 KB Output is correct
2 Correct 29 ms 55100 KB Output is correct
3 Correct 30 ms 54988 KB Output is correct
4 Correct 30 ms 55120 KB Output is correct
5 Correct 29 ms 55124 KB Output is correct
6 Correct 28 ms 55080 KB Output is correct
7 Correct 27 ms 55124 KB Output is correct
8 Correct 29 ms 55144 KB Output is correct
9 Correct 29 ms 55156 KB Output is correct
10 Correct 29 ms 55224 KB Output is correct
11 Correct 30 ms 55316 KB Output is correct
12 Correct 30 ms 55376 KB Output is correct
13 Correct 28 ms 55236 KB Output is correct
14 Correct 34 ms 55244 KB Output is correct
15 Correct 35 ms 55280 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55060 KB Output is correct
2 Correct 31 ms 55036 KB Output is correct
3 Correct 31 ms 55072 KB Output is correct
4 Correct 30 ms 55088 KB Output is correct
5 Correct 30 ms 54988 KB Output is correct
6 Correct 29 ms 55104 KB Output is correct
7 Correct 31 ms 55080 KB Output is correct
8 Correct 29 ms 55124 KB Output is correct
9 Correct 32 ms 55216 KB Output is correct
10 Correct 29 ms 55252 KB Output is correct
11 Correct 33 ms 55312 KB Output is correct
12 Correct 30 ms 55264 KB Output is correct
13 Correct 34 ms 55252 KB Output is correct
14 Correct 31 ms 55332 KB Output is correct
15 Correct 31 ms 55284 KB Output is correct
16 Correct 33 ms 55508 KB Output is correct
17 Correct 34 ms 56276 KB Output is correct
18 Correct 36 ms 57568 KB Output is correct
19 Correct 38 ms 57900 KB Output is correct
20 Correct 38 ms 57928 KB Output is correct
21 Correct 32 ms 55716 KB Output is correct
22 Correct 36 ms 57692 KB Output is correct
23 Correct 37 ms 57444 KB Output is correct
24 Correct 39 ms 57804 KB Output is correct
25 Correct 40 ms 58020 KB Output is correct
26 Correct 38 ms 57900 KB Output is correct
27 Correct 40 ms 57932 KB Output is correct
28 Correct 41 ms 58044 KB Output is correct
29 Correct 45 ms 58196 KB Output is correct
30 Correct 41 ms 57968 KB Output is correct
31 Correct 40 ms 58220 KB Output is correct
32 Correct 42 ms 58244 KB Output is correct
33 Correct 47 ms 58728 KB Output is correct
34 Correct 59 ms 58808 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55024 KB Output is correct
2 Correct 30 ms 55080 KB Output is correct
3 Correct 30 ms 55100 KB Output is correct
4 Correct 29 ms 55112 KB Output is correct
5 Correct 28 ms 55124 KB Output is correct
6 Correct 31 ms 55124 KB Output is correct
7 Correct 28 ms 55080 KB Output is correct
8 Correct 30 ms 55040 KB Output is correct
9 Correct 30 ms 55136 KB Output is correct
10 Correct 30 ms 55260 KB Output is correct
11 Correct 33 ms 55236 KB Output is correct
12 Correct 32 ms 55252 KB Output is correct
13 Correct 30 ms 55252 KB Output is correct
14 Correct 30 ms 55312 KB Output is correct
15 Correct 31 ms 55252 KB Output is correct
16 Correct 31 ms 55400 KB Output is correct
17 Correct 33 ms 56288 KB Output is correct
18 Correct 38 ms 57532 KB Output is correct
19 Correct 40 ms 57936 KB Output is correct
20 Correct 41 ms 58012 KB Output is correct
21 Correct 29 ms 55692 KB Output is correct
22 Correct 37 ms 57692 KB Output is correct
23 Correct 37 ms 57420 KB Output is correct
24 Correct 43 ms 57804 KB Output is correct
25 Correct 39 ms 57896 KB Output is correct
26 Correct 37 ms 57972 KB Output is correct
27 Correct 38 ms 57944 KB Output is correct
28 Correct 39 ms 58128 KB Output is correct
29 Correct 44 ms 58252 KB Output is correct
30 Correct 42 ms 57932 KB Output is correct
31 Correct 38 ms 58272 KB Output is correct
32 Correct 38 ms 58068 KB Output is correct
33 Correct 47 ms 58768 KB Output is correct
34 Correct 48 ms 58784 KB Output is correct
35 Correct 47 ms 58052 KB Output is correct
36 Correct 36 ms 56788 KB Output is correct
37 Correct 54 ms 59472 KB Output is correct
38 Correct 53 ms 59316 KB Output is correct
39 Correct 57 ms 59412 KB Output is correct
40 Correct 56 ms 59340 KB Output is correct
41 Correct 53 ms 59384 KB Output is correct
42 Correct 44 ms 58384 KB Output is correct
43 Correct 40 ms 58416 KB Output is correct
44 Correct 43 ms 58376 KB Output is correct
45 Correct 67 ms 62168 KB Output is correct
46 Correct 54 ms 62156 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 54996 KB Output is correct
2 Correct 30 ms 55012 KB Output is correct
3 Correct 30 ms 55060 KB Output is correct
4 Correct 31 ms 55064 KB Output is correct
5 Correct 29 ms 55040 KB Output is correct
6 Correct 28 ms 55024 KB Output is correct
7 Correct 29 ms 55108 KB Output is correct
8 Correct 29 ms 55076 KB Output is correct
9 Correct 31 ms 55124 KB Output is correct
10 Correct 32 ms 55188 KB Output is correct
11 Correct 34 ms 55304 KB Output is correct
12 Correct 29 ms 55252 KB Output is correct
13 Correct 31 ms 55224 KB Output is correct
14 Correct 34 ms 55324 KB Output is correct
15 Correct 32 ms 55312 KB Output is correct
16 Correct 33 ms 55372 KB Output is correct
17 Correct 33 ms 56268 KB Output is correct
18 Correct 40 ms 57516 KB Output is correct
19 Correct 39 ms 57920 KB Output is correct
20 Correct 42 ms 57884 KB Output is correct
21 Correct 33 ms 55660 KB Output is correct
22 Correct 35 ms 57668 KB Output is correct
23 Correct 36 ms 57420 KB Output is correct
24 Correct 40 ms 57804 KB Output is correct
25 Correct 38 ms 57956 KB Output is correct
26 Correct 37 ms 57892 KB Output is correct
27 Correct 37 ms 57980 KB Output is correct
28 Correct 43 ms 58120 KB Output is correct
29 Correct 59 ms 58260 KB Output is correct
30 Correct 39 ms 57960 KB Output is correct
31 Correct 38 ms 58332 KB Output is correct
32 Correct 38 ms 58088 KB Output is correct
33 Correct 52 ms 58764 KB Output is correct
34 Correct 51 ms 58780 KB Output is correct
35 Correct 44 ms 58060 KB Output is correct
36 Correct 38 ms 56768 KB Output is correct
37 Correct 48 ms 59504 KB Output is correct
38 Correct 52 ms 59464 KB Output is correct
39 Correct 51 ms 59344 KB Output is correct
40 Correct 49 ms 59308 KB Output is correct
41 Correct 55 ms 59464 KB Output is correct
42 Correct 49 ms 58440 KB Output is correct
43 Correct 41 ms 58444 KB Output is correct
44 Correct 41 ms 58456 KB Output is correct
45 Correct 55 ms 62132 KB Output is correct
46 Correct 53 ms 62172 KB Output is correct
47 Correct 169 ms 79100 KB Output is correct
48 Correct 133 ms 89532 KB Output is correct
49 Correct 153 ms 92300 KB Output is correct
50 Correct 163 ms 95588 KB Output is correct
51 Correct 217 ms 100248 KB Output is correct
52 Correct 221 ms 100352 KB Output is correct
53 Correct 184 ms 97744 KB Output is correct
54 Correct 168 ms 97388 KB Output is correct
55 Correct 170 ms 97376 KB Output is correct
56 Correct 174 ms 98588 KB Output is correct
57 Correct 299 ms 104844 KB Output is correct
58 Correct 166 ms 97732 KB Output is correct
59 Correct 198 ms 98072 KB Output is correct
60 Correct 215 ms 98716 KB Output is correct
61 Correct 195 ms 98116 KB Output is correct
62 Correct 203 ms 101092 KB Output is correct
63 Correct 216 ms 120088 KB Output is correct
64 Correct 225 ms 125636 KB Output is correct
65 Correct 271 ms 133696 KB Output is correct
66 Correct 440 ms 154552 KB Output is correct
67 Correct 433 ms 154244 KB Output is correct