제출 #332992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332992		Cantfindme	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	490 ms	46572 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
const int maxn = 30010;
const int INF = INT_MAX/2;

typedef pair<int, pi> pp;


int n,doges;

vector <int> bufflist[maxn];
vector <int> smalldogs[maxn];
const int len = 174;

int dist[maxn][len+10];
int stp,endp;

int32_t main() {
	FAST
	cin >> n >> doges;
		
	for (int i =0;i<doges;i++) {
		int pos, jump; cin >> pos >> jump;
		if (i == 0) stp = pos;
		if (i == 1) endp = pos;
		
		if (jump < len) {
			smalldogs[pos].push_back(jump);
		} else {
			bufflist[pos].push_back(jump);
		}
	}
	
	memset(dist, -1, sizeof dist);
	deque <pp> pq;
	
	pq.push_front(pp(0,pi(stp,0)));
	dist[stp][0] = 0;
	
	while (!pq.empty()) {
		pp cur = pq.front(); pq.pop_front();
		int d = cur.f, pos = cur.s.f, jump = cur.s.s;
		//cout << pos << " " << jump << " " << d << "\n";
		
		if (jump == 0) {
			if (d != dist[pos][0]) continue;
			
			for (auto i: bufflist[pos]) {
				if (pos + i < n) pq.push_back(pp(d+1,pi(pos + i,i)));
				if (pos - i >= 0) pq.push_back(pp(d+1,pi(pos - i,-i)));
			}
			
			for (auto i: smalldogs[pos]) {
				if (dist[pos][i] == -1 or dist[pos][i] > d) {
					dist[pos][i] = d;
					pq.push_front(pp(d, pi(pos,i)));
				}
			}
		
		} else if (jump > 0 and jump < len) {
			if (d != dist[pos][jump]) continue;
			if (dist[pos][0] == -1 or dist[pos][0] > d) {
				dist[pos][0] = d;
				pq.push_front(pp(d,pi(pos,0)));
			}
			
			int newp = pos + jump;
			if (newp < n) {
				if (dist[newp][jump] == -1 or dist[newp][jump] > d + 1) {
					dist[newp][jump] = d + 1;
					pq.push_back(pp(d+1, pi(newp,jump)));
				}
			}
			
			newp = pos - jump;
			if (newp >= 0) {
				if (dist[newp][jump] == -1 or dist[newp][jump] > d + 1) {
					dist[newp][jump] = d + 1;
					pq.push_back(pp(d + 1, pi(newp,jump)));
				}
			}
		
		} else { //On a buff dog train
			
			//Get off
			if (dist[pos][0] == -1 or dist[pos][0] > d) {
				dist[pos][0] = d;
				pq.push_front(pp(d,pi(pos,0)));
			}
			
			//Continue train
			if (jump > 0 and pos + jump < n) pq.push_back(pp(d+1,pi(pos + jump,jump)));
			else if (jump < 0 and pos + jump >= 0) pq.push_back(pp(d+1,pi(pos + jump,jump)));
		}
		
		
	}
	
	cout << dist[endp][0];
	
}

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