Submission #33791

#	Time	Username	Problem	Language	Result	Execution time	Memory
33791		sinhriv	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1000 ms	110640 KiB

skyscraper

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 30030;
const int base = 180;
 
	#define Data pair < int, pair < int, int > >


int n, m;
int f[N][base];
int d[N][base];
vector < int > doges[N];
list < Data > que[N * 20];
 
bool minimize(int &u, int v){
	if(u > v){
		u = v;
		return true;
	}
	return false;
}
 
int main(){
	if(fopen("1.inp", "r")){
		freopen("1.inp", "r", stdin);
	}
 
	scanf("%d%d", &n, &m);
 
	int start = -1, finish = -1;
 
	for(int i = 1; i <= m; ++i){
		int u, v;
		scanf("%d%d", &u, &v);
 
		if(start == -1){
			start = u;
		}
		else if(finish == -1){
			finish = u;
		}
 
		doges[u].push_back(v);
	}
 
 
	priority_queue < Data, vector < Data >, greater < Data > > heap;
 
	memset(f, 60, sizeof f);
	f[start][0] = 0;


 
	que[0].emplace_back(0, make_pair(start, 0));
	for(int t = 0; t < N * 20; ++t){
		for(auto p : que[t]){
			int u = p.second.first;;
			int x = p.second.second;
			heap.pop();
	 
			if(d[u][x] == 1) continue;
			d[u][x] = 1;
	 
	 
			if(u == finish){
				cout << f[u][x];
				return 0;
			}
	 
			if(u - x >= 0){
				if(minimize(f[u - x][x], f[u][x] + 1)){
				 que[f[u - x][x]].emplace_back(f[u - x][x], make_pair(u - x, x));
				}
			}
			if(u + x < n){
				if(minimize(f[u + x][x], f[u][x] + 1)){
					que[f[u + x][x]].emplace_back(f[u + x][x], make_pair(u + x, x));
				}
			}
			
			for(int val : doges[u]){
				if(val < base){
					if(u - val >= 0){
						if(minimize(f[u - val][val], f[u][x] + 1)){
							que[f[u - val][val]].emplace_back(f[u - val][val], make_pair(u - val, val));
						}
					}
					if(u + val < n){
						if(minimize(f[u + val][val], f[u][x] + 1)){
							que[f[u + val][val]].emplace_back(f[u + val][val], make_pair(u + val, val));
						}
					}
				}
				else{
					for(int t = 1; t < N / base; ++t){
						if(u - t * val < 0 && u + t * val >= n) break;
						if(u - t * val >= 0){
							if(minimize(f[u - t * val][0], f[u][x] + t)){
								que[f[u - t * val][0]].emplace_back(f[u - t * val][0], make_pair(u - t * val, 0));
							}
						}
						if(u + t * val < n){
							if(minimize(f[u + t * val][0], f[u][x] + t)){
								que[f[u + t * val][0]].emplace_back(f[u + t * val][0], make_pair(u + t * val, 0));
							}
						}
					}
				}
			}
		}
	}
	cout << -1;
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:27:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("1.inp", "r", stdin);
                               ^
skyscraper.cpp:30:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
skyscraper.cpp:36:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
                        ^

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