Submission #23564

#	Time	Username	Problem	Language	Result	Execution time	Memory
23564		samir_droubi	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	373 ms	112020 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int mxn=(1e5)+5;
vector<pair<int,int> >gr[mxn];
set<int>a[mxn];
set<pair<int,int> >s;
int st,en;
int dis[mxn];
set<pair<int,int> >::iterator it;
set<int>::iterator itt;
void dijk()
{
	for(int i=0;i<mxn;++i)dis[i]=(1e9);
	dis[st]=0;
	s.insert({0,st});
	while(!s.empty())
	{
		it=s.begin();
		int v=it->second;
		int d=it->first;
		s.erase(it);
		for(int i=0;i<gr[v].size();++i)
		{
			int u=gr[v][i].first;
			int w=gr[v][i].second;
			if(d+w<dis[u])
			{
				dis[u]=d+w;
				s.insert({d+w,u});
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i)
	{
		int b,p;
		scanf("%d%d",&b,&p);
		a[b].insert(p);
		if(i==0)st=b;
		if(i==1)en=b;
	}

	for(int i=0;i<n;++i)
	{
		itt=a[i].begin();
		for(itt;itt!=a[i].end();++itt)
		{
			int p=*itt;
			for(int j=1;i+(j*p)<n;++j)
			{
				int cur=i+(j*p);
				gr[i].push_back({cur,j});
				if(a[cur].count(p))break;
			}
		}
	}

	for(int i=n-1;i>=0;--i)
	{
		itt=a[i].begin();
		for(itt;itt!=a[i].end();++itt)
		{
			int p=*itt;
			for(int j=1;i-(j*p)>=0;++j)
			{
				int cur=i-(j*p);
				gr[i].push_back({cur,j});
				if(a[cur].count(p))break;
			}
		}
	}

	dijk();
	if(dis[en]==(1e9))dis[en]=-1;
	printf("%d\n",dis[en]);
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void dijk()':
skyscraper.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<gr[v].size();++i)
                ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:50:10: warning: statement has no effect [-Wunused-value]
   for(itt;itt!=a[i].end();++itt)
          ^
skyscraper.cpp:65:10: warning: statement has no effect [-Wunused-value]
   for(itt;itt!=a[i].end();++itt)
          ^
skyscraper.cpp:37:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
skyscraper.cpp:41:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&b,&p);
                      ^

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