Submission #794752

#	Time	Username	Problem	Language	Result	Execution time	Memory
794752		bane	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	446 ms	7752 KiB

skyscraper

    #include<bits/stdc++.h>
    using namespace std;
     
    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
     
    void solve(){
    	int n, m;
    	cin >> n >> m;
    	vector<pair<int,int>>monsters(m);
    	vector<unordered_set<int>>pos(n);
    	for (int i = 0; i < m; i++){
    		int b, p;
    		cin >> b >> p;
    		pos[b].insert(p);
    		monsters[i] = {b,p};
    	}
    	vector<long long>dp(n, (long long)1e18);
    	dp[monsters[0].first] = 0;
		vector<int>vis(n, 0);
    	priority_queue<pair<long long,int>>pq;
    	pq.push({0,monsters[0].first});
    	while(!pq.empty()){
    		long long dst = -pq.top().first;
    		int b = pq.top().second;
    		pq.pop();
    		//node + pow * x = mn
    		if (dp[b] != dst)continue;
    		if (b == monsters[1].first){
    			cout << dst << endl;
    			return ;
    		}
			if (vis[b])continue;
			vis[b] = 1;
    		for (auto p : pos[b]){
				for (int i = 1; b + i * p < n; i++){
    				int right = b + i * p;
    				
    				if (dp[right] > dst + i){
    					dp[right] = dst + i;
    					pq.push({-dst-i,right});
    				}

    			}
				for (int i = 1; b - i * p >= 0; i++){
					int left = b - i * p;
    				if (left >= 0){
    					if (dp[left] > dst + i){
    						dp[left] = dst + i;
    						pq.push({-dst-i,left});
    					}
    				}  
				}
    		}
    	}
    	cout << - 1 << endl;
    }
     
    int main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	cout.tie(0);
    	solve();
    	return 0;
    }

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