Submission #108068

#	Time	Username	Problem	Language	Result	Execution time	Memory
108068		autumn_eel	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	19 ms	19376 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];

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[0][0]=0;
	deque<P>que;
	que.push_back(P(0,0));
	while(!que.empty()){
		P p=que.front();que.pop_front();
		if(p.second==0){
			for(int i:v[p.first]){
				if(d[p.first][i]>d[p.first][p.second]){
					d[p.first][i]=d[p.first][p.second];
					que.push_front(P(p.first,i));
				}
			}
		}
		else{
			int v;
			if((v=p.first-p.second)>=0&&d[v][p.second]>d[p.first][p.second]+1){
				d[v][p.second]=d[p.first][p.second]+1;
				que.push_back(P(v,p.second));
			}
			if((v=p.first+p.second)<n&&d[v][p.second]>d[p.first][p.second]+1){
				d[v][p.second]=d[p.first][p.second]+1;
				que.push_back(P(v,p.second));
			}
			if(d[p.first][0]>d[p.first][p.second]){
				d[p.first][0]=d[p.first][p.second];
				que.push_front(P(p.first,0));
			}
		}
	}
	cout<<*min_element(d[1],d[1]+n)<<endl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:15: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: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43