Submission #761682

#	Time	Username	Problem	Language	Result	Execution time	Memory
761682		MetalPower	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1086 ms	82812 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;

int l = 0, r = -1;
pair<pair<int, int>, int> BFS[3000001];
 
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);
	}
	
	BFS[++r] = make_pair(make_pair(st, 0), js);
	while(l <= r) {
		int a, b, c;
		a = BFS[l].fi.fi;
		b = BFS[l].fi.se;
		c = BFS[l].se;
	//	cout<<a<<" "<<b<<" "<
		l++;

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