제출 #152168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152168		songc	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1084 ms	73856 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];
unordered_set<int> dchk[30303];
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[S].find(v) == dchk[S].end()){
			Q.push_back((Data){S, v, 0});
			dchk[S].insert(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[T.x].find(v) == dchk[T.x].end()){
					Q.push_front((Data){T.x, v, T.d});
					dchk[T.x].insert(v);
				}
			}
			bchk[T.x] = true;
		}

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

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

	puts("-1");
	return 0;
}

컴파일 시 표준 에러 (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