Submission #761666

#	Time	Username	Problem	Language	Result	Execution time	Memory
761666		MetalPower	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1097 ms	87064 KiB

skyscraper

# include <bits/stdc++.h>
# define fi first
# define se second
# define ll long long
using namespace std;
 
const int sq = 200;
vector<int> dg[30001];
map<ll , int> jp;
 
int st, js, ed;
int rc[30001];
bool ex[30001];
map<pair<int, int>, int> vis;
 
ll ch(int a, int b) {
	return (1ll * 1e9 * 1ll * a) + (1ll * b);	
}
 
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();

		if(vis[make_pair(a, c)]) continue;
		vis[make_pair(a, c)] = 1;
		
		rc[a] = min(rc[a], b);
		if(a == ed) break;
		if(a - c >= 0 && jp[ch(a - c, c)] == 0) {
			BFS.push(make_pair(make_pair(a - c, b + 1), c));
			jp[ch(a - c, c)] = 1;
		}
		if(a + c < N && jp[ch(a + c, c)] == 0) {
			BFS.push(make_pair(make_pair(a+c, b + 1), c));
			jp[ch(a + c, c)] = 1;
		}

		if(ex[a]) continue;
		ex[a] = true;
		
		for(int k=0;k<dg[a].size();k++) {
			
			c = dg[a][k];
			if(a - c >= 0 && jp[ch(a - c, c)] == 0) {
				BFS.push(make_pair(make_pair(a - c, b + 1), c));
				jp[ch(a - c, c)] = 1;
			}
			if(a + c < N && jp[ch(a + c, c)] == 0) {
				BFS.push(make_pair(make_pair(a+c, b + 1), c));
				jp[ch(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:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int k=0;k<dg[a].size();k++) {
      |               ~^~~~~~~~~~~~~
skyscraper.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  scanf("%d %d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   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