제출 #1288176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288176		gustavo_d	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1097 ms	94116 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,inline-functions")

#define fi first
#define sc second

typedef long long ll;

const int MAXN = 30000;
const int MAXM = 30000;

bool liberated[MAXN];
int jump[MAXM];
vector<int> in[MAXN];
bitset<MAXM> vis[MAXN];

queue<ll> bfs;
int n;

void liberate(int i, int d) {
    if (liberated[i]) return;
    liberated[i] = true;
    for (int v : in[i]) {
        if (vis[i][v]) continue;
        bfs.push(i + (v << 15) + ((ll)d << 30));
        vis[i][v] = true;
    }
    in[i].clear();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int m; cin >> n >> m;
    int pos, pos1, pos0;
    for (int i=0; i<m; i++) {
        cin >> pos >> jump[i];
        if (i == 0) pos0 = pos;
        if (i == 1) {
            pos1 = pos;
            continue;
        }
        in[pos].push_back(i);
    }

    liberate(pos0, 0);
    ll MASK15 = (1 << 15)-1;
    while (!bfs.empty()) {
        ll vtx = bfs.front();
        int p = vtx & MASK15, v = (vtx >> 15) & MASK15, d = (vtx >> 30);
        // cout << p << ' ' << v << ':' << d << '\n';
        bfs.pop();
        if (p == pos1) {
            cout << d << '\n';
            return 0;
        }
        if (p - jump[v] >= 0 and !vis[p-jump[v]][v]) {
            vis[p-jump[v]][v] = true;
            bfs.push(p - jump[v] + (v << 15) + ((ll)(d+1) << 30));
            liberate(p - jump[v], d+ 1);
        }
        if (p + jump[v] < n and !vis[p+jump[v]][v]) {
            vis[p+jump[v]][v] = true;
            bfs.push(p + jump[v] + (v << 15) + ((ll)(d+1) << 30));
            liberate(p + jump[v], d + 1);
        }
    }
    cout << -1 << '\n';

    return 0;
}

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