Submission #761628

#	Time	Username	Problem	Language	Result	Execution time	Memory
761628		KN200711	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1071 ms	33796 KiB

skyscraper

# include <bits/stdc++.h>
# include <unordered_map>
# define fi first
# define se second
using namespace std;

const int sq = 200;
vector<int> dg[30001];
map< pair<int, int> , int> jp;

int st, js, ed;
int rc[30001];

int main() {
	int N, M;
	scanf("%d %d", &N, &M);
	
	for(int i=0;i<N;i++) rc[i] = 1e9;
	for(int i=0;i<M;i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		if(i == 0) {
			st = a;
			js = b;
		} else if(i == 1) ed = a;
		else dg[a].push_back(b);
	}
	
	queue< pair<pair<int, int>, int> > BFS;
	BFS.push(make_pair(make_pair(st, 0), js));
	while(BFS.size()) {
		int a, b, c;
		a = BFS.front().fi.fi;
		b = BFS.front().fi.se;
		c = BFS.front().se;
	//	cout<<a<<" "<<b<<" "<
		BFS.pop();
		
		rc[a] = min(rc[a], b);
		if(a - c >= 0 && jp[make_pair(a - c, c)] == 0) {
			BFS.push(make_pair(make_pair(a - c, b + 1), c));
			jp[make_pair(a - c, c)] = 1;
		}
		if(a + c < N && jp[make_pair(a + c, c)] == 0) {
			BFS.push(make_pair(make_pair(a+c, b + 1), c));
			jp[make_pair(a + c, c)] = 1;
		}
		for(int k=0;k<dg[a].size();k++) {
			c = dg[a][k];
			if(a - c >= 0 && jp[make_pair(a - c, c)] == 0) {
				BFS.push(make_pair(make_pair(a - c, b + 1), c));
				jp[make_pair(a - c, c)] = 1;
			}
			if(a + c < N && jp[make_pair(a + c, c)] == 0) {
				BFS.push(make_pair(make_pair(a+c, b + 1), c));
				jp[make_pair(a + c, c)] = 1;
			}
		}
	}
	if(rc[ed] == 1e9) rc[ed] = -1;
	printf("%d\n", rc[ed]);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int k=0;k<dg[a].size();k++) {
      |               ~^~~~~~~~~~~~~
skyscraper.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d %d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   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