Submission #761771

#	Time	Username	Problem	Language	Result	Execution time	Memory
761771		KN200711	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	252 ms	112196 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];
bitset<30001> jp[30001];

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

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

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