Submission #40712

#	Time	Username	Problem	Language	Result	Execution time	Memory
40712		IvanC	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	521 ms	38724 KiB

skyscraper

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define MAXN 2010
#define MP make_pair
using namespace std;
typedef pair<int,int> ii;
int grafo[MAXN][MAXN];
int origem,destino,n,m,processado[MAXN];
int main(){
	memset(grafo,-1,sizeof(grafo));
	scanf("%d %d",&n,&m);
	n--;
	for(int i=0;i<m;i++){
		int ini,percorre;
		scanf("%d %d",&ini,&percorre);
		if(i == 0) origem = ini;
		if(i == 1){
			destino = ini;
			continue;
		}
		for(int j = 1;ini - percorre*j >= 0;j++){
			if(grafo[ini][ini - percorre*j] == -1){
				grafo[ini][ini - percorre*j] = j;
			}
			else{
				grafo[ini][ini - percorre*j] = min(j,grafo[ini][ini - percorre*j]);
			}
		}
		for(int j = 1;ini + percorre*j <= n;j++){
			if(grafo[ini][ini + percorre*j] == -1){
				grafo[ini][ini + percorre*j] = j;
			}
			else{
				grafo[ini][ini + percorre*j] = min(j,grafo[ini][ini + percorre*j]);
			}
		}
	}
	priority_queue<ii, vector<ii> , greater<ii> > Dijkstra;
	Dijkstra.push(MP(0,origem));
	while(!Dijkstra.empty()){
		ii davez = Dijkstra.top();
		Dijkstra.pop();
		int v = davez.second, percorrido = davez.first;
		if(processado[v]) continue;
		processado[v] = 1;
		if(v == destino	){
			printf("%d\n",percorrido);
			return 0;
		}
		for(int i=0;i<=n;i++){
			if(!processado[i] && grafo[v][i] != -1){
				Dijkstra.push(MP(percorrido + grafo[v][i],i));
			}
		}
	}
	printf("-1\n");
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:13:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
skyscraper.cpp:17:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&ini,&percorre);
                                ^

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