Submission #132200

#	Time	Username	Problem	Language	Result	Execution time	Memory
132200		asifthegreat	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	515 ms	262148 KiB

skyscraper

#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
 
const int N = 30003;
 
struct node{
	int at,cost;
	node(int a, int b){
		at = a,cost = b;
	}
};
 
bool operator<(node A,node B){
	return A.cost > B.cost;
}
 
vector<pii>edges,graph[N];
int dist[N];
map<pii,bool>vis;
 
int dijkstra(int s,int dst,int n)
{
	priority_queue<node>pq;
	for(int i = 0; i < n;i++)dist[i] = 999999999;
	dist[s] = 0;
	pq.push(node(s,0));
	while(!pq.empty()){
		node u = pq.top();
		//printf("%d\n",u.at);
		pq.pop();
		if(u.cost != dist[u.at])continue;
		for(pii e: graph[u.at]){
			//printf("%d: %d -- %d,%d\n",u.at,e.first,dist[e.first],u.cost+e.second);
			if(dist[e.first] > u.cost+e.second){
				dist[e.first] = u.cost+e.second;
				pq.push(node(e.first,dist[e.first]));
			}
		}
		//exit(0);
	}
	return dist[dst];
}
 
int main(int argc, char const *argv[])
{
	int n,m,b,a;
	scanf("%d%d",&n,&m);
	int src = -1,destination = -1;
	for(int i = 0; i < m;i++){
		scanf("%d%d",&a,&b);
		if(vis[{a,b}])continue;
		vis[{a,b}] = vis[{b,a}] = true;
		if(i == 0)src = a;
		if(i == 1)destination = a;
		int x = 1;
		while(a+b*x < n){
			graph[a].push_back({a+b*x,x});
			x++;
		}
		x = 1;
		while(a-b*x >= 0){
			graph[a].push_back({a-b*x,x});
			x++;
		}
	}
	//printf("%d %d\n",src,destination);exit(0);
	int k = dijkstra(src,destination,n);
	if(k == 999999999)printf("-1\n");
	else printf("%d\n",k);
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main(int, const char**)':
skyscraper.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~

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