Submission #185630

#	Time	Username	Problem	Language	Result	Execution time	Memory
185630		dndhk	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	34 ms	16760 KiB

skyscraper

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 2000;
const int INF = 10000000;

int dp[MAX_N+1][MAX_N+1];
int N, M;
vector<int> gp[MAX_N+1];
int s, e, d;
bool chk[MAX_N+1];
deque<pii> dq;

bool check(int x, int y){
	if(x==e){
		printf("%d", y);
		return true;
	}
	chk[x] = true;
	for(int i : gp[x]){
		if(dp[x][i]>y){
			dp[x][i] = y;
			dq.pb({x, i});
		}
	}
	return false;
}

int main(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<M; i++){
		int a, b; scanf("%d%d", &a, &b);
		a++;
		gp[a].pb(b);
		if(i==0){
			s = a;
			d = b;
		}else if(i==1){
			e = a;
		}
	}
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			dp[i][j] = INF;
		}
	}
	dq.pb({s, d});
	if(check(s, 0)){
		return 0;
	}
	dp[s][d] = 0;
	while(!dq.empty()){
		pii now = dq.front(); dq.pop_front();
		if(now.first+now.second<=N){
			if(dp[now.first+now.second][now.second]>dp[now.first][now.second]+1){
				dp[now.first+now.second][now.second] = dp[now.first][now.second] + 1;
				dq.pb({now.first+now.second, now.second});
				if(!chk[now.first+now.second]){
					if(check(now.first+now.second, dp[now.first][now.second]+1)){
						return 0;
					}
				}
			}
		}
		if(now.first-now.second>=1){
			if(dp[now.first-now.second][now.second]>dp[now.first][now.second]+1){
				dp[now.first-now.second][now.second] = dp[now.first][now.second] + 1;
				dq.pb({now.first-now.second, now.second});
				if(!chk[now.first-now.second]){
					if(check(now.first-now.second, dp[now.first-now.second][now.second])){
						return 0;
					}
				}
			}
		}
	}
	printf("-1");
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:37: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:39:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; 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