Submission #152155

#	Time	Username	Problem	Language	Result	Execution time	Memory
152155		songc	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1080 ms	39364 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M, S, E;
vector<int> D[30303];
set<pii> dchk;
bool bchk[30303];

struct Data{
	int x, y, d;
};
deque<Data> Q;

int main(){
	scanf("%d %d", &N, &M);
	
	int x, y;
	scanf("%d %d", &x, &y);
	D[x].push_back(y);
	S = x;

	scanf("%d %d", &x, &y);
	D[x].push_back(y);
	E = x;

	for (int i=3; i<=M; i++){
		scanf("%d %d", &x, &y);
		D[x].push_back(y);
	}

	for (int v : D[S]){
		if (dchk.find(pii(S, v)) == dchk.end()){
			Q.push_back((Data){S, v, 0});
			dchk.insert(pii(S, v));
		}
	}
	bchk[S] = true;

	while (!Q.empty()){
		Data T = Q.front();
		Q.pop_front();
		if (T.x == E){
			printf("%d\n", T.d);
			return 0;
		}
		if (!bchk[T.x]){
			for (int v : D[T.x]){
				if (dchk.find(pii(T.x, v)) == dchk.end()){
					Q.push_front((Data){T.x, v, T.d});
					dchk.insert(pii(T.x, v));
				}
			}
			bchk[T.x] = true;
		}

		if (T.x-T.y >= 0 && dchk.find(pii(T.x-T.y, T.y)) == dchk.end()){
			Q.push_back((Data){T.x-T.y, T.y, T.d+1});
			dchk.insert(pii(T.x-T.y, T.y));
		}

		if (T.x+T.y < N && dchk.find(pii(T.x+T.y, T.y)) == dchk.end()){
			Q.push_back((Data){T.x+T.y, T.y, T.d+1});
			dchk.insert(pii(T.x+T.y, T.y));
		}
	}

	puts("-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("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &x, &y);
  ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &x, &y);
  ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

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