Submission #83292

#	Time	Username	Problem	Language	Result	Execution time	Memory
83292		farukkastamonuda	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	259 ms	13516 KiB

skyscraper

#include <bits/stdc++.h>
#define li 30005
#define inf 100000000009
#define md 1000000007
#define lo long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ii pair<int, pair<int,int> >
using namespace std;
lo int n,m,B[li],P[li],tut=inf;
queue< pair<lo int, pair<lo int,lo int> > > q;
unordered_map<lo int,lo int> vis[li];
vector<lo int> v[li];
int main(){
	scanf("%lld %lld",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%lld %lld",&B[i],&P[i]);
		v[B[i]].pb(i);
	}
	q.push(mp(1,mp(B[0],P[0])));
	while(!q.empty()){
		ii temp=q.front();
		q.pop();
		lo int seh=temp.se.fi;
		lo int cst=temp.fi;
		lo int zip=temp.se.se;
		//if(vis[seh][zip]==0) vis[seh][zip]=inf;
		if(vis[seh][zip]) continue;
		//printf("%d %d %d\n",seh,zip,cst);
		vis[seh][zip]=cst;
		if(seh==B[1]){
			tut=min(tut,cst);
			continue;
		}
		for(int i=0;i<(int)v[seh].size();i++){
			int ind=v[seh][i];
			if(P[ind]!=zip){
				q.push(mp(cst,mp(seh,P[ind])));
			}
		}
		if(seh+zip<n) q.push(mp(cst+1,mp(seh+zip,zip)));
		if(seh-zip>=0) q.push(mp(cst+1,mp(seh-zip,zip)));
	}
	if(tut>=inf) tut=0;
	printf("%lld\n",tut-1);
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~
skyscraper.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&B[i],&P[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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