제출 #1326955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326955		kutomei3	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	200 ms	112196 KiB

skyscraper

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


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

    int n, m;
    cin >> n >> m;

    vector<bitset<30002>> vis(30002);

    vector<int> ap[n + 1];
    int po, st, k1;
    for (int i = 0; i < m; i++) {
        int u, k;
        cin >> u >> k;
        ap[u].push_back(k);
        if (i == 0) st = u, k1 = k;
        if (i == 1) po = u;
    }

    int pa[2] = {-1, 1};

    queue<array<int, 3>> qu;
    qu.push({st, k1, 0});

    vis[st][k1] = 1;

    while (qu.size())
    {
        auto [u, k, p] = qu.front();
        qu.pop();

        //cout << "HERE";

        //cout << u << ' ' << k << ' ' << p << '\n';

        if (u == po) {
            cout << p;
            return 0;
        }

        for (auto& d : pa) {
            int np = u - d * k;
            //cout << "HERE";
            if (np < 0 || np >= n || vis[np][k]) continue;
            vis[np][k] = true;
            //cout << "HERE";
            qu.push({np, k, p + 1});
        }

        for (auto& o : ap[u]) {
            for (auto& d : pa) {
                int np = u - d * o;
                if (np < 0 || np >= n || vis[np][o]) continue;
                vis[np][o] = true;
                qu.push({np, o, p + 1});
            }
        }
    }

    cout << -1;

    return 0;
}

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