oj.uz

Submission #744061

# Submission time Handle Problem Language Result Execution time Memory
744061 2023-05-18T07:46:04 Z fanwen Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 126 ms 196952 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 = 7e6 + 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 98 ms 192036 KB Output is correct
2 Correct 97 ms 191988 KB Output is correct
3 Correct 95 ms 192072 KB Output is correct
4 Correct 94 ms 192056 KB Output is correct
5 Correct 88 ms 192276 KB Output is correct
6 Correct 87 ms 192164 KB Output is correct
7 Correct 88 ms 192084 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 192056 KB Output is correct
2 Correct 86 ms 192068 KB Output is correct
3 Correct 87 ms 192204 KB Output is correct
4 Correct 93 ms 192088 KB Output is correct
5 Correct 86 ms 192172 KB Output is correct
6 Correct 89 ms 192192 KB Output is correct
7 Correct 88 ms 192116 KB Output is correct
8 Correct 93 ms 192404 KB Output is correct
9 Correct 94 ms 192700 KB Output is correct
10 Correct 90 ms 193076 KB Output is correct
11 Correct 91 ms 193168 KB Output is correct
12 Correct 94 ms 193100 KB Output is correct
13 Correct 92 ms 193092 KB Output is correct
14 Correct 93 ms 193144 KB Output is correct
15 Correct 96 ms 193200 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 192068 KB Output is correct
2 Correct 88 ms 192032 KB Output is correct
3 Correct 101 ms 192088 KB Output is correct
4 Correct 92 ms 192148 KB Output is correct
5 Correct 101 ms 192188 KB Output is correct
6 Correct 107 ms 192208 KB Output is correct
7 Correct 89 ms 192124 KB Output is correct
8 Correct 95 ms 192444 KB Output is correct
9 Correct 99 ms 192724 KB Output is correct
10 Correct 102 ms 193048 KB Output is correct
11 Correct 105 ms 193092 KB Output is correct
12 Correct 96 ms 193024 KB Output is correct
13 Correct 98 ms 193044 KB Output is correct
14 Correct 100 ms 193136 KB Output is correct
15 Correct 102 ms 193064 KB Output is correct
16 Correct 99 ms 193524 KB Output is correct
17 Incorrect 115 ms 196952 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 192104 KB Output is correct
2 Correct 106 ms 191980 KB Output is correct
3 Correct 94 ms 192100 KB Output is correct
4 Correct 102 ms 192128 KB Output is correct
5 Correct 100 ms 192152 KB Output is correct
6 Correct 98 ms 192200 KB Output is correct
7 Correct 101 ms 192180 KB Output is correct
8 Correct 97 ms 192432 KB Output is correct
9 Correct 94 ms 192676 KB Output is correct
10 Correct 112 ms 193116 KB Output is correct
11 Correct 107 ms 193088 KB Output is correct
12 Correct 107 ms 193076 KB Output is correct
13 Correct 126 ms 193124 KB Output is correct
14 Correct 106 ms 193156 KB Output is correct
15 Correct 110 ms 193148 KB Output is correct
16 Correct 107 ms 193504 KB Output is correct
17 Incorrect 115 ms 196856 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 192144 KB Output is correct
2 Correct 99 ms 192056 KB Output is correct
3 Correct 95 ms 192048 KB Output is correct
4 Correct 92 ms 192076 KB Output is correct
5 Correct 111 ms 192208 KB Output is correct
6 Correct 98 ms 192204 KB Output is correct
7 Correct 112 ms 192092 KB Output is correct
8 Correct 94 ms 192476 KB Output is correct
9 Correct 98 ms 192668 KB Output is correct
10 Correct 97 ms 193104 KB Output is correct
11 Correct 94 ms 193096 KB Output is correct
12 Correct 92 ms 193112 KB Output is correct
13 Correct 97 ms 193092 KB Output is correct
14 Correct 119 ms 193088 KB Output is correct
15 Correct 101 ms 193152 KB Output is correct
16 Correct 96 ms 193508 KB Output is correct
17 Incorrect 101 ms 196932 KB Output isn't correct
18 Halted 0 ms 0 KB -