Submission #253932

#	Time	Username	Problem	Language	Result	Execution time	Memory
253932		ChrisT	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	31 ms	33920 KiB

skyscraper

#include<bits/stdc++.h>
#define hsh(x,y) (x)<<15|(y)
using namespace std;
const int MN = 30005;
int b[MN], p[MN];
pair<int,int> dq[11000000];
bitset<100000000> 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:11: 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: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43