제출 #1178480

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178480		peteza	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	238 ms	162152 KiB

skyscraper

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

int n, m, a[50005], b[50005];
bitset<50005> mp[50005];
deque<pair<pair<int, int>, int>> q;
vector<int> todeploy[50005];
bool puengkery[50005];

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0;i<m;i++) {
        cin >> a[i] >> b[i];
        todeploy[a[i]].push_back(b[i]);
    }
    q.emplace_back(make_pair(a[0], b[0]), 0);
    //puengkery[a[0]] = 1;
    //for(auto &e:todeploy[a[0]]) q.emplace_back(make_pair(a[0], e), 0);
    while(!q.empty()) {
        auto e = q.front(); q.pop_front();
        //res = mp[e.first.first].find(e.first.second);
        if(mp[e.first.first][e.first.second]) continue;
        mp[e.first.first][e.first.second] = 1;
        if(e.first.first == a[1]) {
            cout << e.second;
            return 0;
        }
        if(!puengkery[e.first.first]) {
            puengkery[e.first.first] = 1;
            for(auto &E:todeploy[e.first.first]) q.emplace_front(make_pair(e.first.first, E), e.second);
        }
        if(e.first.first - e.first.second >= 0) q.emplace_back(make_pair(e.first.first - e.first.second, e.first.second), e.second+1);
        if(e.first.first + e.first.second < n)  q.emplace_back(make_pair(e.first.first + e.first.second, e.first.second), e.second+1);
        
    }
    cout << -1;
}

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