Submission #1164271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164271		pacman	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	495 ms	113036 KiB

skyscraper

#include <bits/stdc++.h>
#define int long long int

using namespace std;

const int maxn = 30005, oo = 1e18;

int n, m, ans = oo, st, fn;
int pos[maxn], pov[maxn];
vector<int> adj[maxn];
bitset<maxn> bt[maxn];
bool mark[maxn];

void in(){
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		cin >> pos[i] >> pov[i];
		adj[pos[i]].push_back(pov[i]);
	}
	st = pos[0], fn = pos[1];
}

struct state{
	int c, b, p;
	bool operator>(const state &a) const{
		return c > a.c;
	}
};

void djkasra(){
	priority_queue<state, vector<state>, greater<state>> pq;
	
	mark[st] = true;
	for(auto u : adj[st]){
		if(!bt[st][u]){
			bt[st][u] = 1;
			pq.push({0, st, u});
		}
	}

	while(!pq.empty()){
		state v = pq.top();
		pq.pop();
		if(v.b == fn){
			ans = min(ans, v.c);
		}
        int nxt = v.b - v.p;
        if(nxt >= 0){
            if(!bt[nxt][v.p]){
                bt[nxt][v.p] = 1;
                pq.push({v.c + 1, nxt, v.p});
            }
            if(!mark[nxt]){
                for(auto u : adj[nxt]){
                    if(!bt[nxt][u]){
                        bt[nxt][u] = 1;
                        pq.push({v.c + 1, nxt, u});
                    }
                }
                mark[nxt] = true;
            }
        }
        nxt = v.b + v.p;
        if(nxt < n){
            if(!bt[nxt][v.p]){
                bt[nxt][v.p] = 1;
                pq.push({v.c + 1, nxt, v.p});
            }
            if(!mark[nxt]){
                for(auto u : adj[nxt]){
                    if(!bt[nxt][u]){
                        bt[nxt][u] = 1;
                        pq.push({v.c + 1, nxt, u});
                    }
                }
                mark[nxt] = true;
            }
        }
	}
}

void Engine(){
	djkasra();
}

void out(){
	if(ans == oo) {
		cout << "-1\n";
		return;
	}
	cout << ans << "\n";
}

int32_t main(){
	ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);

	in();
	Engine();
	out();

	return 0;
}

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