oj.uz

Submission #744059

# Submission time Handle Problem Language Result Execution time Memory
744059 2023-05-18T07:44:51 Z fanwen Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 33 ms 55252 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(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 29 ms 54996 KB Output is correct
2 Correct 28 ms 54984 KB Output is correct
3 Correct 29 ms 55124 KB Output is correct
4 Correct 28 ms 55116 KB Output is correct
5 Correct 28 ms 55020 KB Output is correct
6 Correct 29 ms 55088 KB Output is correct
7 Correct 30 ms 55088 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 54996 KB Output is correct
2 Correct 28 ms 55028 KB Output is correct
3 Correct 33 ms 55112 KB Output is correct
4 Correct 28 ms 55076 KB Output is correct
5 Correct 30 ms 55104 KB Output is correct
6 Correct 32 ms 55028 KB Output is correct
7 Correct 28 ms 55088 KB Output is correct
8 Correct 28 ms 55112 KB Output is correct
9 Incorrect 29 ms 55104 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 54988 KB Output is correct
2 Correct 29 ms 55180 KB Output is correct
3 Correct 31 ms 55100 KB Output is correct
4 Correct 29 ms 55124 KB Output is correct
5 Correct 28 ms 55124 KB Output is correct
6 Correct 28 ms 55124 KB Output is correct
7 Correct 30 ms 55012 KB Output is correct
8 Correct 27 ms 55124 KB Output is correct
9 Incorrect 29 ms 55072 KB Output isn't correct
10 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 29 ms 54996 KB Output is correct
3 Correct 30 ms 55124 KB Output is correct
4 Correct 28 ms 55024 KB Output is correct
5 Correct 28 ms 55040 KB Output is correct
6 Correct 30 ms 55112 KB Output is correct
7 Correct 28 ms 55252 KB Output is correct
8 Correct 30 ms 55116 KB Output is correct
9 Incorrect 30 ms 55136 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 55088 KB Output is correct
2 Correct 28 ms 54996 KB Output is correct
3 Correct 28 ms 55124 KB Output is correct
4 Correct 29 ms 55084 KB Output is correct
5 Correct 27 ms 55000 KB Output is correct
6 Correct 33 ms 55092 KB Output is correct
7 Correct 32 ms 55104 KB Output is correct
8 Correct 27 ms 55124 KB Output is correct
9 Incorrect 28 ms 55104 KB Output isn't correct
10 Halted 0 ms 0 KB -