Submission #260032

#	Time	Username	Problem	Language	Result	Execution time	Memory
260032		pure_mem	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1100 ms	39160 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[300][N];
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));
	set< pair< int, pair<int, int> > > st;
	dst[0][start] = 0;
	st.insert(MP(0, MP(start, 0)));

	while(!st.empty()){
		pair< int, pair<int, int> > temp = *st.begin();
		st.erase(st.begin());

		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[power][pos] > dst_pos){
						st.erase(MP(dst[power][pos], MP(pos, power)));
						dst[power][pos] = dst_pos;
						st.insert(MP(dst_pos, MP(pos, power)));
					}		
				}
				else{
					for(int j = 1;pos - j * power >= 0;j++){
						int next = pos - j * power;
						if(dst[0][next] > dst_pos + j){
							st.erase(MP(dst[0][next], MP(next, 0)));	
							dst[0][next] = dst_pos + j;
							st.insert(MP(dst[0][next], MP(next, 0)));	
						}
					}
					for(int j = 1;pos + j * power < n;j++){
						int next = pos + j * power;
						if(dst[0][next] > dst_pos + j){
							st.erase(MP(dst[0][next], MP(next, 0)));	
							dst[0][next] = dst_pos + j;
							st.insert(MP(dst[0][next], MP(next, 0)));	
						}
					}
				}
			}	
		}
		else{
			if(dst[0][pos] > dst_pos){
				st.erase(MP(dst[0][pos], MP(pos, 0)));
				dst[0][pos] = dst_pos;
				st.insert(MP(dst_pos, MP(pos, 0)));
			}
  			if(pos - power >= 0 && dst[power][pos - power] > dst_pos + 1){
  				st.erase(MP(dst[power][pos - power], MP(pos - power, power)));
  				dst[power][pos - power] = dst_pos + 1;
  				st.insert(MP(dst_pos + 1, MP(pos - power, power)));
  			}
  			if(pos + power < n && dst[power][pos + power] > dst_pos + 1){
  				st.erase(MP(dst[power][pos + power], MP(pos + power, power)));
  				dst[power][pos + power] = dst_pos + 1;
  				st.insert(MP(dst_pos + 1, MP(pos + power, power)));
  			}	
		}
	}

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

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