Submission #253935

#	Time	Username	Problem	Language	Result	Execution time	Memory
253935		ChrisT	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	1 ms	1024 KiB

skyscraper

#include<bits/stdc++.h>
#define hsh(x,y) (y)<<15|(x)
using namespace std;
const int MN = 30005;
int b[MN], p[MN];
pair<int,int> dq[11000000];
bitset<500000000> vis;
vector<int> st[MN];
int main () {
  int n,m;
  scanf ("%d %d",&n,&m);
  for (int i = 0; i < m; i++) {
	scanf ("%d %d",&b[i],&p[i]);
	st[b[i]].push_back(i);
  }
  int l = n, r = l + 1;
  dq[l] = {hsh(b[0],p[0]),0};
  while (l < r) {
	int cur = dq[l].first>>15, power = dq[l].first & 0x7FFF, dist = dq[l].second; ++l;
	if (cur == b[1]) return !printf ("%d\n",dist);
	for (int i : st[cur]) if (!vis[hsh(cur,p[i])]) {
	  vis[hsh(cur,p[i])] = 1;
	  dq[--l] = {hsh(cur,p[i]),dist};
	}
	st[cur].clear();
	if (cur >= power && !vis[hsh(cur-power,power)]) {
	  vis[hsh(cur-power,power)] = 1;
	  dq[r++] = {hsh(cur-power,power),dist+1};
	}
	if (cur + power < n && !vis[hsh(cur+power,power)]) {
	  vis[hsh(cur+power,power)] = 1;
	  dq[r++] = {hsh(cur+power,power),dist+1};
	}
  }
  printf ("-1\n");
  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:11:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d",&n,&m);
   ~~~~~~^~~~~~~~~~~~~~~
skyscraper.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d",&b[i],&p[i]);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~

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