Submission #108075

#	Time	Username	Problem	Language	Result	Execution time	Memory
108075		autumn_eel	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	82 ms	39672 KiB

skyscraper

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int>P;
typedef long long ll;

int b[50000],t[50000];
int d[2200][2200];
vector<int>v[2200];

struct st{
	int a,b,c;
};
bool operator<(st a,st b){
	return a.c>b.c;
}
int main(){
	int n,m;cin>>n>>m;
	rep(i,m){
		scanf("%d%d",&b[i],&t[i]);
		v[b[i]].push_back(t[i]);
	}
	memset(d,0x3f,sizeof(d));
	d[b[0]][0]=0;
	priority_queue<st>que;
	que.push({b[0],0,0});
	while(!que.empty()){
		st p=que.top();que.pop();
		int c=d[p.a][p.b];
		if(c!=p.c)continue;
		if(p.b==0){
			for(int i:v[p.a]){
				if(d[p.a][i]>c){
					d[p.a][i]=c;
					que.push({p.a,i,c});
				}
			}
		}
		else{
			int v;
			if((v=p.a-p.b)>=0&&d[v][p.b]>c+1){
				d[v][p.b]=c+1;
				que.push({v,p.b,c+1});
			}
			if((v=p.a+p.b)<n&&d[v][p.b]>c+1){
				d[v][p.b]=c+1;
				que.push({v,p.b,c+1});
			}
			if(d[p.a][0]>c){
				d[p.a][0]=c;
				que.push({p.a,0,c});
			}
		}
	}
	int ans=*min_element(d[b[1]],d[b[1]]+2200);
	if(ans==INF)puts("-1");
	else cout<<ans<<endl;
}

Compilation message (stderr)

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

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