oj.uz

답안 #839233

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
839233 2023-08-29T09:19:15 Z tch1cherin Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 113 ms 226548 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX LLONG_MAX

const int MAX_N = 30000;
const int C = 300;
vector<pair<int, int>> G[MAX_N * C];
int B[MAX_N], P[MAX_N];
int D[MAX_N * C];

void connect(int u, int v, int w, bool directed = false) {
  G[u].push_back({v, w});
  if (!directed) {
    G[v].push_back({u, w});
  }
}

int32_t main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    cin >> B[i] >> P[i];
    if (P[i] >= C) {
      for (int j = B[i] % P[i]; j < N; j += P[i]) {
        connect(B[i], j, abs(j - B[i]) / P[i], true);
      }
    } else {
      connect(B[i], B[i] + P[i] * N, 0, true);
    }
  }
  for (int i = 0; i < N; i++) {
    for (int power = 1; power < C; power++) {
      if (i - power >= 0) {
        connect(i + power * N, i + power * (N - 1), 1, true);
        connect(i + power * N, i - power, 1, true);
      }
      if (i + power < N) {
        connect(i + power * N, i + power * (N + 1), 1, true);
        connect(i + power * N, i + power, 1, true);
      }
    }
  }
  fill(D, D + MAX_N, INT_MAX);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
  Q.push({D[B[0]] = 0, B[0]});
  while (!Q.empty()) {
    auto [d, u] = Q.top();
    Q.pop();
    if (d > D[u]) {
      continue;
    }
    for (auto [v, w] : G[u]) {
      if (D[u] + w < D[v]) {
        Q.push({D[v] = D[u] + w, v}); 
      }
    }
  }
  cout << (D[B[1]] == INT_MAX ? -1 : D[B[1]]) << "\n";
}

Compilation message

skyscraper.cpp:4: warning: "INT_MAX" redefined
    4 | #define INT_MAX LLONG_MAX
      | 
In file included from /usr/include/c++/10/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
                 from skyscraper.cpp:1:
/usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:120: note: this is the location of the previous definition
  120 | #define INT_MAX __INT_MAX__
      |

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 211788 KB Output is correct
2 Correct 83 ms 211812 KB Output is correct
3 Correct 82 ms 211900 KB Output is correct
4 Correct 84 ms 211844 KB Output is correct
5 Correct 85 ms 211868 KB Output is correct
6 Correct 82 ms 211788 KB Output is correct
7 Correct 82 ms 211788 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 211788 KB Output is correct
2 Correct 83 ms 211788 KB Output is correct
3 Correct 83 ms 211788 KB Output is correct
4 Correct 83 ms 211788 KB Output is correct
5 Correct 83 ms 211792 KB Output is correct
6 Correct 85 ms 211916 KB Output is correct
7 Correct 83 ms 211788 KB Output is correct
8 Correct 83 ms 211928 KB Output is correct
9 Correct 96 ms 212044 KB Output is correct
10 Correct 84 ms 212360 KB Output is correct
11 Correct 84 ms 212428 KB Output is correct
12 Correct 84 ms 212300 KB Output is correct
13 Correct 88 ms 212372 KB Output is correct
14 Correct 86 ms 212428 KB Output is correct
15 Correct 84 ms 212388 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 211900 KB Output is correct
2 Correct 83 ms 211836 KB Output is correct
3 Correct 87 ms 211788 KB Output is correct
4 Correct 82 ms 212004 KB Output is correct
5 Correct 83 ms 211872 KB Output is correct
6 Correct 83 ms 211888 KB Output is correct
7 Correct 87 ms 211864 KB Output is correct
8 Correct 84 ms 211916 KB Output is correct
9 Correct 84 ms 212044 KB Output is correct
10 Correct 84 ms 212364 KB Output is correct
11 Correct 84 ms 212436 KB Output is correct
12 Correct 84 ms 212300 KB Output is correct
13 Correct 84 ms 212464 KB Output is correct
14 Correct 84 ms 212428 KB Output is correct
15 Correct 86 ms 212592 KB Output is correct
16 Correct 87 ms 213552 KB Output is correct
17 Incorrect 111 ms 226508 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 211852 KB Output is correct
2 Correct 83 ms 211844 KB Output is correct
3 Correct 81 ms 211848 KB Output is correct
4 Correct 83 ms 211900 KB Output is correct
5 Correct 85 ms 211812 KB Output is correct
6 Correct 85 ms 211864 KB Output is correct
7 Correct 86 ms 211920 KB Output is correct
8 Correct 83 ms 211916 KB Output is correct
9 Correct 85 ms 212040 KB Output is correct
10 Correct 87 ms 212276 KB Output is correct
11 Correct 84 ms 212428 KB Output is correct
12 Correct 84 ms 212300 KB Output is correct
13 Correct 97 ms 212300 KB Output is correct
14 Correct 87 ms 212424 KB Output is correct
15 Correct 85 ms 212392 KB Output is correct
16 Correct 87 ms 213556 KB Output is correct
17 Incorrect 113 ms 226548 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 211788 KB Output is correct
2 Correct 87 ms 211964 KB Output is correct
3 Correct 82 ms 211784 KB Output is correct
4 Correct 83 ms 211788 KB Output is correct
5 Correct 82 ms 211840 KB Output is correct
6 Correct 83 ms 211876 KB Output is correct
7 Correct 85 ms 211836 KB Output is correct
8 Correct 82 ms 211912 KB Output is correct
9 Correct 83 ms 212044 KB Output is correct
10 Correct 87 ms 212276 KB Output is correct
11 Correct 83 ms 212392 KB Output is correct
12 Correct 97 ms 212276 KB Output is correct
13 Correct 84 ms 212300 KB Output is correct
14 Correct 84 ms 212428 KB Output is correct
15 Correct 84 ms 212356 KB Output is correct
16 Correct 89 ms 213644 KB Output is correct
17 Incorrect 111 ms 226508 KB Output isn't correct
18 Halted 0 ms 0 KB -