Submission #847209

#	Time	Username	Problem	Language	Result	Execution time	Memory
847209		voi	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	374 ms	132296 KiB

skyscraper

#include <bits/stdc++.h>
#define ii pair <int, int>
#define iii pair <ii, int>
#define fi first.first
#define se first.second
#define th second

using namespace std;
#define task "code"
#define all(s) s.begin(), s.end()

typedef long long ll;

const int ar = 3e5+2;
const ll mod = 998244353;
const int oo = 1e9;
const int LG = 9;

const int BLOCK = 100;
int n, m, b[ar], p[ar], d[ar][BLOCK + 1];
priority_queue <iii, vector <iii>, greater <iii>> q;
vector <int> pos[ar];

void dijkstra() {
    q.push({{0, b[0]}, 0});
    int ans = 1e9;
    memset(d, 0x3f, sizeof d);
    d[b[0]][0] = 0;
    while (!q.empty()) {
        iii x = q.top();
        int dis = x.fi , pk = x.th , i = x.se;
        if (i == b[1]) ans = min(ans , dis);
        q.pop();
        if (dis != d[i][pk]) continue;
        if (pk == 0) {
            for (auto x : pos[i])
            if (p[x] <= BLOCK) {
                if (d[i][p[x]] > dis) {
                    d[i][p[x]] = dis;
                    q.push({{dis , i} , p[x]});
                }
            } else {
                int pp = p[x];
                int cnt = 0;
                for (int x = i ; x < n ; x += pp)  {
                    if (d[x][0] > dis + cnt) {
                        d[x][0] = dis + cnt;
                        q.push({{dis + cnt , x} , 0});
                    }
                    cnt++;
                }
                cnt = 0;
                for (int x = i ; x >= 0 ; x -= pp) {
                    if (d[x][0] > dis + cnt) {
                        d[x][0] = dis + cnt;
                        q.push({{dis + cnt , x} , 0});
                    }
                    cnt++;
                }

            }
        } else {
            if (i + pk < n && d[i + pk][pk] > dis + 1) {
                d[i + pk][pk] = dis + 1;
                q.push({{dis + 1 , i + pk} , pk});
            }
            if (i - pk >= 0 && d[i - pk][pk] > dis + 1) {
                d[i - pk][pk] = dis + 1;
                q.push({{dis + 1 , i - pk} , pk});
            }
            if (d[i][0] > dis) {
                d[i][0] = dis;
                q.push({{dis , i} , 0});
            }
        }
    }
    if (ans == 1e9) cout << -1;
    else cout << ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    cin >> n >> m;
    for(int i = 0; i < m; ++i)
        cin >> b[i] >> p[i], pos[b[i]].push_back(i);

    dijkstra();

    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43