Submission #740634

#	Time	Username	Problem	Language	Result	Execution time	Memory
740634		abczz	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	365 ms	7952 KiB

skyscraper

#include <iostream>
#include <map>
#include <unordered_map>
#include <queue>
#include <vector>
#include <array>
#define ll long long

using namespace std;

map <array<ll, 2>, ll> mp;
unordered_map <ll, ll> mp2;
queue <array<ll, 3> > Q;
vector <bool> dp[30000];
vector <ll> adj[30000];
bool visited[30000];
ll n, m, k, x, B[30000], P[30000], id[30000], cnt;
int main() {
  cin >> n >> m;
  for (int i=0; i<m; ++i) {
    cin >> B[i] >> P[i];
    adj[B[i]].push_back(i);
    k = B[i]%P[i];
    auto itr = mp.find({P[i], k});
    if (itr == mp.end()) {
      for (int j=0; k+j*P[i]<n; ++j) {
        dp[cnt].push_back(0);
      }
      mp[{P[i], k}] = id[i] = cnt++;
    }
    else id[i] = itr->second;
  }
  Q.push({B[0], 0, 0});
  dp[id[0]][B[0]/P[0]] = true;
  while (!Q.empty()) {
    auto [u, z, w] = Q.front();
    Q.pop();
    if (u == B[1]) {
      cout << w << '\n';
      return 0;
    }
    if (u + P[z] < n && !dp[id[z]][u/P[z]+1]) {
      dp[id[z]][u/P[z]+1] = true;
      Q.push({u+P[z], z, w+1});
    }
    if (u - P[z] >= 0 && !dp[id[z]][u/P[z]-1]) {
      dp[id[z]][u/P[z]-1] = true;
      Q.push({u-P[z], z, w+1});
    }
    if (!visited[u]) {
      visited[u] = true;
      for (auto v : adj[u]) {
        dp[id[v]][u/P[v]] = true;
        if (u + P[v] < n && !dp[id[v]][u/P[v]+1]) {
          dp[id[v]][u/P[v]+1] = true;
          Q.push({u+P[v], v, w+1});
        }
        if (u - P[v] >= 0 && !dp[id[v]][u/P[v]-1]) {
          dp[id[v]][u/P[v]-1] = true;
          Q.push({u-P[v], v, w+1});
        }
      }
    }
  }
  cout << "-1\n";
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:36:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     auto [u, z, w] = Q.front();
      |          ^

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