oj.uz

Submission #555450

# Submission time Handle Problem Language Result Execution time Memory
555450 2022-05-01T00:18:04 Z SmolBrain Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
 986 ms 198364 KB 
// Om Namah Shivaya
// GM in 94 days

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define endl '\n'
#define pb push_back
#define conts continue
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define ff first
#define ss second
#define ceil2(x,y) ((x+y-1) / (y))
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x <<" = "; print(x); cout << endl
#else
#define debug(x)
#endif

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

bool iseven(ll n) {if ((n & 1) == 0) return true; return false;}

void print(ll t) {cout << t;}
void print(int t) {cout << t;}
void print(string t) {cout << t;}
void print(char t) {cout << t;}
void print(double t) {cout << t;}
void print(ld t) {cout << t;}

template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(pair <T, V> p) {cout << "{"; print(p.ff); cout << ","; print(p.ss); cout << "}";}
template <class T> void print(vector <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(set <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(multiset <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T, class V> void print(map <T, V> v) {cout << "[ "; for (auto i : v) {print(i); cout << " ";} cout << "]";}
template<typename T> void amin(T &a, T b) { a = min(a, b); }
template<typename T> void amax(T &a, T b) { a = max(a, b); }

void usaco(string filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

const int MOD = 1e9 + 7;
const int maxn = 3e4 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = ll(1e18) + 5;
const int block_size = 175;

vector<array<int, 3>> adj[maxn][block_size];
bool vis[maxn][block_size];
int dis[maxn][block_size];

void solve(int test_case)
{
    // editorial approach
    int n, m; cin >> n >> m;
    vector<pii> a(m);

    rep(i, m) {
        int b, p; cin >> b >> p;
        a[i] = {b, p};

        if (p < block_size) {
            adj[b][0].pb({b, p, 0});
        }
        else {
            int w = 0;

            for (int j = b - p; j >= 0; j -= p) {
                w++;
                adj[b][0].pb({j, 0, w});
            }

            w = 0;

            for (int j = b + p; j < n; j += p) {
                w++;
                adj[b][0].pb({j, 0, w});
            }
        }
    }

    priority_queue< array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>> > pq;
    rep(i, n) rep(j, block_size) dis[i][j] = inf1;

    if (a[0].ss < block_size) {
        pq.push({0, a[0].ff, a[0].ss});
        dis[a[0].ff][a[0].ss] = 0;
    }
    else {
        pq.push({0, a[0].ff, 0});
        dis[a[0].ff][0] = 0;
    }

    auto add = [&](int cost, int b, int p) {
        if (cost < dis[b][p]) {
            dis[b][p] = cost;
            pq.push({cost, b, p});
        }
    };

    while (!pq.empty()) {
        auto [cost, b, p] = pq.top();
        pq.pop();

        if (vis[b][p]) conts;
        vis[b][p] = 1;

        if (b == a[1].ff) {
            cout << cost << endl;
            return;
        }

        // add edge to dummy vertex of b
        add(cost, b, 0);

        // go 1 step left / 1 step right
        if (p > 0) {
            if (b - p >= 0) add(cost + 1, b - p, p);
            if (b + p < n) add(cost + 1, b + p, p);
        }

        // traverse other edges and add them
        for (auto [b2, p2, w] : adj[b][p]) {
            add(cost + w, b2, p2);
        }
    }

    cout << -1 << endl;
}

int main()
{
    chrono::steady_clock::time_point begin = chrono::steady_clock::now();

    fastio;

    int t = 1;
    // cin >> t;
    rep1(i, t) {
        solve(i);
    }

    chrono::steady_clock::time_point end = chrono::steady_clock::now();
    cerr << "[Finished in " << chrono::duration_cast<chrono::microseconds>(end - begin).count() / 1000 << "ms]" << endl;

    return 0;
}

Compilation message

skyscraper.cpp: In function 'void usaco(std::string)':
skyscraper.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 123576 KB Output is correct
2 Correct 59 ms 123616 KB Output is correct
3 Correct 59 ms 123592 KB Output is correct
4 Correct 57 ms 123552 KB Output is correct
5 Correct 56 ms 123520 KB Output is correct
6 Correct 60 ms 123532 KB Output is correct
7 Correct 59 ms 123556 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 123564 KB Output is correct
2 Correct 57 ms 123600 KB Output is correct
3 Correct 57 ms 123536 KB Output is correct
4 Correct 57 ms 123592 KB Output is correct
5 Correct 59 ms 123564 KB Output is correct
6 Correct 57 ms 123596 KB Output is correct
7 Correct 61 ms 123596 KB Output is correct
8 Correct 59 ms 123584 KB Output is correct
9 Correct 58 ms 123564 KB Output is correct
10 Correct 59 ms 123784 KB Output is correct
11 Correct 55 ms 123732 KB Output is correct
12 Correct 58 ms 123756 KB Output is correct
13 Correct 59 ms 123680 KB Output is correct
14 Correct 64 ms 123772 KB Output is correct
15 Correct 58 ms 123724 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 123624 KB Output is correct
2 Correct 59 ms 123620 KB Output is correct
3 Correct 60 ms 123516 KB Output is correct
4 Correct 57 ms 123568 KB Output is correct
5 Correct 58 ms 123628 KB Output is correct
6 Correct 56 ms 123532 KB Output is correct
7 Correct 60 ms 123560 KB Output is correct
8 Correct 60 ms 123596 KB Output is correct
9 Correct 57 ms 123616 KB Output is correct
10 Correct 58 ms 123688 KB Output is correct
11 Correct 57 ms 123724 KB Output is correct
12 Correct 58 ms 123656 KB Output is correct
13 Correct 58 ms 123716 KB Output is correct
14 Correct 58 ms 123728 KB Output is correct
15 Correct 59 ms 123796 KB Output is correct
16 Correct 58 ms 123696 KB Output is correct
17 Correct 60 ms 124332 KB Output is correct
18 Correct 63 ms 124796 KB Output is correct
19 Correct 58 ms 124956 KB Output is correct
20 Correct 59 ms 125388 KB Output is correct
21 Correct 58 ms 123828 KB Output is correct
22 Correct 59 ms 124756 KB Output is correct
23 Correct 60 ms 124928 KB Output is correct
24 Correct 61 ms 125260 KB Output is correct
25 Correct 61 ms 125356 KB Output is correct
26 Correct 59 ms 125404 KB Output is correct
27 Correct 59 ms 125332 KB Output is correct
28 Correct 62 ms 125388 KB Output is correct
29 Correct 69 ms 125356 KB Output is correct
30 Correct 62 ms 125264 KB Output is correct
31 Correct 63 ms 125284 KB Output is correct
32 Correct 63 ms 125256 KB Output is correct
33 Correct 73 ms 125444 KB Output is correct
34 Correct 69 ms 125392 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 123584 KB Output is correct
2 Correct 58 ms 123596 KB Output is correct
3 Correct 57 ms 123596 KB Output is correct
4 Correct 58 ms 123548 KB Output is correct
5 Correct 57 ms 123536 KB Output is correct
6 Correct 63 ms 123552 KB Output is correct
7 Correct 59 ms 123516 KB Output is correct
8 Correct 63 ms 123600 KB Output is correct
9 Correct 57 ms 123576 KB Output is correct
10 Correct 58 ms 123656 KB Output is correct
11 Correct 57 ms 123700 KB Output is correct
12 Correct 56 ms 123688 KB Output is correct
13 Correct 58 ms 123772 KB Output is correct
14 Correct 60 ms 123764 KB Output is correct
15 Correct 58 ms 123712 KB Output is correct
16 Correct 58 ms 123700 KB Output is correct
17 Correct 59 ms 124292 KB Output is correct
18 Correct 59 ms 124796 KB Output is correct
19 Correct 59 ms 125040 KB Output is correct
20 Correct 60 ms 125388 KB Output is correct
21 Correct 58 ms 123868 KB Output is correct
22 Correct 60 ms 124756 KB Output is correct
23 Correct 61 ms 124940 KB Output is correct
24 Correct 59 ms 125264 KB Output is correct
25 Correct 59 ms 125344 KB Output is correct
26 Correct 60 ms 125388 KB Output is correct
27 Correct 61 ms 125396 KB Output is correct
28 Correct 61 ms 125392 KB Output is correct
29 Correct 67 ms 125260 KB Output is correct
30 Correct 64 ms 125308 KB Output is correct
31 Correct 70 ms 125356 KB Output is correct
32 Correct 60 ms 125288 KB Output is correct
33 Correct 71 ms 125388 KB Output is correct
34 Correct 66 ms 125368 KB Output is correct
35 Correct 65 ms 125600 KB Output is correct
36 Correct 59 ms 124604 KB Output is correct
37 Correct 68 ms 126668 KB Output is correct
38 Correct 66 ms 126540 KB Output is correct
39 Correct 64 ms 126144 KB Output is correct
40 Correct 65 ms 126232 KB Output is correct
41 Correct 65 ms 126540 KB Output is correct
42 Correct 66 ms 126016 KB Output is correct
43 Correct 71 ms 126008 KB Output is correct
44 Correct 64 ms 126024 KB Output is correct
45 Correct 116 ms 128608 KB Output is correct
46 Correct 86 ms 128564 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 123596 KB Output is correct
2 Correct 58 ms 123576 KB Output is correct
3 Correct 67 ms 123516 KB Output is correct
4 Correct 58 ms 123560 KB Output is correct
5 Correct 59 ms 123592 KB Output is correct
6 Correct 58 ms 123568 KB Output is correct
7 Correct 57 ms 123540 KB Output is correct
8 Correct 58 ms 123536 KB Output is correct
9 Correct 60 ms 123624 KB Output is correct
10 Correct 57 ms 123636 KB Output is correct
11 Correct 57 ms 123724 KB Output is correct
12 Correct 58 ms 123744 KB Output is correct
13 Correct 57 ms 123752 KB Output is correct
14 Correct 58 ms 123732 KB Output is correct
15 Correct 58 ms 123728 KB Output is correct
16 Correct 58 ms 123688 KB Output is correct
17 Correct 59 ms 124308 KB Output is correct
18 Correct 65 ms 124824 KB Output is correct
19 Correct 60 ms 125012 KB Output is correct
20 Correct 58 ms 125388 KB Output is correct
21 Correct 58 ms 123800 KB Output is correct
22 Correct 58 ms 124860 KB Output is correct
23 Correct 59 ms 124920 KB Output is correct
24 Correct 60 ms 125252 KB Output is correct
25 Correct 60 ms 125368 KB Output is correct
26 Correct 60 ms 125344 KB Output is correct
27 Correct 57 ms 125388 KB Output is correct
28 Correct 58 ms 125356 KB Output is correct
29 Correct 67 ms 125264 KB Output is correct
30 Correct 60 ms 125248 KB Output is correct
31 Correct 64 ms 125260 KB Output is correct
32 Correct 62 ms 125248 KB Output is correct
33 Correct 74 ms 125448 KB Output is correct
34 Correct 68 ms 125428 KB Output is correct
35 Correct 65 ms 125624 KB Output is correct
36 Correct 59 ms 124604 KB Output is correct
37 Correct 64 ms 126636 KB Output is correct
38 Correct 65 ms 126608 KB Output is correct
39 Correct 65 ms 126156 KB Output is correct
40 Correct 65 ms 126284 KB Output is correct
41 Correct 64 ms 126608 KB Output is correct
42 Correct 65 ms 126076 KB Output is correct
43 Correct 62 ms 125952 KB Output is correct
44 Correct 64 ms 126044 KB Output is correct
45 Correct 119 ms 128572 KB Output is correct
46 Correct 96 ms 128472 KB Output is correct
47 Correct 81 ms 140064 KB Output is correct
48 Correct 78 ms 141244 KB Output is correct
49 Correct 78 ms 142432 KB Output is correct
50 Correct 73 ms 143948 KB Output is correct
51 Correct 97 ms 152216 KB Output is correct
52 Correct 92 ms 152336 KB Output is correct
53 Correct 73 ms 146060 KB Output is correct
54 Correct 73 ms 149220 KB Output is correct
55 Correct 74 ms 149244 KB Output is correct
56 Correct 84 ms 150352 KB Output is correct
57 Correct 69 ms 144456 KB Output is correct
58 Correct 81 ms 150024 KB Output is correct
59 Correct 80 ms 149944 KB Output is correct
60 Correct 81 ms 150480 KB Output is correct
61 Correct 81 ms 150268 KB Output is correct
62 Correct 114 ms 152832 KB Output is correct
63 Correct 160 ms 185296 KB Output is correct
64 Correct 181 ms 198364 KB Output is correct
65 Correct 478 ms 196048 KB Output is correct
66 Correct 986 ms 187200 KB Output is correct
67 Correct 531 ms 186908 KB Output is correct