Submission #1167118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167118		AMnu	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	10 / 100	1 ms	840 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
typedef pair<int,int> pii;

const int MAXN = 3e4;

bitset <30000> bs[MAXN];

int main(){
    ll n, m; cin >> n >> m;
    vector<ll> b(m + 5), p(m + 5);
    for(int i = 1; i <= m; i++) cin >> b[i] >> p[i];
    vector<ll> adj[n + 5];
    for(int i = 1; i <= m; i++){
        adj[b[i]].push_back(p[i]);
    }
    vector<ll> pq[2];
    pq[0].push_back(b[1]);
    for(int dist=0;!pq[dist&1].empty();dist++){
        for (auto idx : pq[dist&1]) {
            if (idx == b[2]) {
                cout << dist << "\n";
                return 0;
            }
            for(auto i : adj[idx]){
                // cout << idx << " " << i << "\n";
                bs[idx][i] = 1;
                if(idx+i < n && !bs[idx+i][i]){
                    bs[idx+i][i] = 1;
                    pq[dist&1^1].push_back(idx+i);
                    adj[idx+i].push_back(i);
                }
                if(idx-i >= 0 && !bs[idx-i][i]){
                    bs[idx-i][i] = 1;
                    pq[dist&1^1].push_back(idx-i);
                    adj[idx-i].push_back(i);
                }
            }
            adj[idx].clear();
        }
        pq[dist&1].clear();
    }
    cout << "-1\n";
}

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