제출 #260037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260037		pure_mem	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1088 ms	37440 KiB

skyscraper

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 3e4, inf = 1e9;
const int bs = 300;

int n, m, dst[N][bs];
vector<int> dog[N];

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

	cin >> n >> m;
	int start = 0, finish = 0;
	for(int i = 0;i < m;i++){
		int x, y;
		cin >> x >> y;
		if(i == 0)
			start = x;
		else if(i == 1)
			finish = x;
	    dog[x].push_back(y);
	}
	memset(dst, 0x3f, sizeof(dst));
	priority_queue < pair< int, pair<int, int> > > st;
	dst[start][0] = 0;
	st.push(MP(0, MP(start, 0)));

	while(!st.empty()){
		pair< int, pair<int, int> > temp = st.top();
		st.pop();

		int dst_pos = -temp.X, pos = temp.Y.X, power = temp.Y.Y;
		
		// cerr << dst_pos << " " << pos << "\n";
		
		if(power == 0){
			for(int it = 0;it < (int)dog[pos].size();it++){
				power = dog[pos][it];
				if(power < bs){
					if(dst[pos][power] > dst_pos){
						dst[pos][power] = dst_pos;
						st.push(MP(-dst_pos, MP(pos, power)));
					}		
				}
				else{
					for(int j = 1;pos - j * power >= 0;j++){
						int next = pos - j * power;
						if(dst[next][0] > dst_pos + j){
							dst[next][0] = dst_pos + j;
							st.push(MP(-dst[next][0], MP(next, 0)));	
						}
					}
					for(int j = 1;pos + j * power < n;j++){
						int next = pos + j * power;
						if(dst[next][0] > dst_pos + j){
							dst[next][0] = dst_pos + j;
							st.push(MP(-dst[next][0], MP(next, 0)));	
						}
					}
				}
			}	
		}
		else{
			if(dst[pos][0] > dst_pos){
				dst[pos][0] = dst_pos;
				st.push(MP(-dst_pos, MP(pos, 0)));
			}
  			if(pos - power >= 0 && dst[pos - power][power] > dst_pos + 1){
  				dst[pos - power][power] = dst_pos + 1;
  				st.push(MP(-dst_pos - 1, MP(pos - power, power)));
  			}
  			if(pos + power < n && dst[pos + power][power] > dst_pos + 1){
  				dst[pos + power][power] = dst_pos + 1;
  				st.push(MP(-dst_pos - 1, MP(pos + power, power)));
  			}	
		}
	}

    cout << (dst[finish][0] >= inf ? -1: dst[finish][0]);
}

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