Submission #695141

#	Time	Username	Problem	Language	Result	Execution time	Memory
695141		NeroZein	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	17 ms	32104 KiB

skyscraper

#include <bits/stdc++.h>
#define int long long 
using namespace std; 

const int N = 2003;
const int M = 30004; 

int n, m;
int b[M];
int p[M];
int cost[N][N];

set<int> v[N];

inline void bfs() {
  queue<pair<int, int>> q;
  memset(cost, -1, sizeof cost);
  q.emplace(b[0], 0);
  cost[b[0]][p[0]] = 0; 
  while (!q.empty()) {
    auto src = q.front();
    q.pop();
    if (src.first == b[1]) {
      cout << src.second; 
      exit(0);
    }
    for (auto c : v[src.first]) {
      int l = src.first - c;
      int r = src.first + c;
      if (l >= 0 && cost[l][c] == -1) {
        cost[l][c] = src.second + 1; 
        q.emplace(l, cost[l][c]);
        v[l].insert(c);
      }
      if (r < n && cost[r][c] == -1) {
        cost[r][c] = src.second + 1;
        q.emplace(r, cost[r][c]);
        v[r].insert(c);
      }
    }
  }
}

signed main() {
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> b[i] >> p[i];
    v[b[i]].insert(p[i]);
  }
  bfs();
  cout << -1 << '\n';
  return 0; 
}

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