oj.uz

Submission #839252

# Submission time Handle Problem Language Result Execution time Memory
839252 2023-08-29T11:04:49 Z tch1cherin Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 422 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 30000;
const int C = 150;
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 * C, 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";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 123596 KB Output is correct
2 Correct 50 ms 123468 KB Output is correct
3 Correct 50 ms 123600 KB Output is correct
4 Correct 51 ms 123596 KB Output is correct
5 Correct 50 ms 123596 KB Output is correct
6 Correct 48 ms 123596 KB Output is correct
7 Correct 49 ms 123596 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 123520 KB Output is correct
2 Correct 48 ms 123596 KB Output is correct
3 Correct 48 ms 123588 KB Output is correct
4 Correct 50 ms 123604 KB Output is correct
5 Correct 50 ms 123596 KB Output is correct
6 Correct 49 ms 123596 KB Output is correct
7 Correct 49 ms 123596 KB Output is correct
8 Correct 49 ms 123596 KB Output is correct
9 Correct 49 ms 123596 KB Output is correct
10 Correct 52 ms 123852 KB Output is correct
11 Correct 49 ms 123852 KB Output is correct
12 Correct 49 ms 123860 KB Output is correct
13 Correct 49 ms 123852 KB Output is correct
14 Correct 50 ms 123948 KB Output is correct
15 Correct 50 ms 123860 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 123596 KB Output is correct
2 Correct 48 ms 123592 KB Output is correct
3 Correct 50 ms 123560 KB Output is correct
4 Correct 51 ms 123504 KB Output is correct
5 Correct 49 ms 123596 KB Output is correct
6 Correct 48 ms 123604 KB Output is correct
7 Correct 49 ms 123604 KB Output is correct
8 Correct 48 ms 123556 KB Output is correct
9 Correct 49 ms 123608 KB Output is correct
10 Correct 49 ms 123852 KB Output is correct
11 Correct 50 ms 123860 KB Output is correct
12 Correct 48 ms 123852 KB Output is correct
13 Correct 50 ms 123908 KB Output is correct
14 Correct 50 ms 123944 KB Output is correct
15 Correct 53 ms 123988 KB Output is correct
16 Correct 52 ms 124620 KB Output is correct
17 Correct 63 ms 128524 KB Output is correct
18 Correct 80 ms 135500 KB Output is correct
19 Correct 83 ms 137164 KB Output is correct
20 Correct 85 ms 137236 KB Output is correct
21 Correct 57 ms 126028 KB Output is correct
22 Correct 81 ms 135632 KB Output is correct
23 Correct 77 ms 134476 KB Output is correct
24 Correct 89 ms 136648 KB Output is correct
25 Correct 83 ms 137292 KB Output is correct
26 Correct 85 ms 137236 KB Output is correct
27 Correct 93 ms 137168 KB Output is correct
28 Correct 87 ms 137316 KB Output is correct
29 Correct 91 ms 137200 KB Output is correct
30 Correct 86 ms 137152 KB Output is correct
31 Correct 93 ms 137168 KB Output is correct
32 Correct 85 ms 137164 KB Output is correct
33 Correct 96 ms 137336 KB Output is correct
34 Correct 94 ms 137292 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 123592 KB Output is correct
2 Correct 49 ms 123496 KB Output is correct
3 Correct 48 ms 123596 KB Output is correct
4 Correct 48 ms 123520 KB Output is correct
5 Correct 49 ms 123608 KB Output is correct
6 Correct 49 ms 123600 KB Output is correct
7 Correct 53 ms 123592 KB Output is correct
8 Correct 51 ms 123596 KB Output is correct
9 Correct 49 ms 123604 KB Output is correct
10 Correct 50 ms 123840 KB Output is correct
11 Correct 52 ms 123944 KB Output is correct
12 Correct 50 ms 123804 KB Output is correct
13 Correct 54 ms 123860 KB Output is correct
14 Correct 52 ms 123852 KB Output is correct
15 Correct 54 ms 123852 KB Output is correct
16 Correct 54 ms 124620 KB Output is correct
17 Correct 67 ms 128452 KB Output is correct
18 Correct 79 ms 135500 KB Output is correct
19 Correct 83 ms 137272 KB Output is correct
20 Correct 84 ms 137244 KB Output is correct
21 Correct 55 ms 126032 KB Output is correct
22 Correct 88 ms 135632 KB Output is correct
23 Correct 87 ms 134432 KB Output is correct
24 Correct 85 ms 136568 KB Output is correct
25 Correct 86 ms 137292 KB Output is correct
26 Correct 84 ms 137168 KB Output is correct
27 Correct 83 ms 137164 KB Output is correct
28 Correct 91 ms 137264 KB Output is correct
29 Correct 91 ms 137176 KB Output is correct
30 Correct 85 ms 137164 KB Output is correct
31 Correct 89 ms 137272 KB Output is correct
32 Correct 86 ms 137240 KB Output is correct
33 Correct 102 ms 137340 KB Output is correct
34 Correct 98 ms 137292 KB Output is correct
35 Correct 95 ms 134140 KB Output is correct
36 Correct 77 ms 131188 KB Output is correct
37 Correct 117 ms 137992 KB Output is correct
38 Correct 128 ms 138444 KB Output is correct
39 Correct 139 ms 138508 KB Output is correct
40 Correct 116 ms 138504 KB Output is correct
41 Correct 112 ms 138532 KB Output is correct
42 Correct 89 ms 137676 KB Output is correct
43 Correct 87 ms 137640 KB Output is correct
44 Correct 86 ms 137716 KB Output is correct
45 Correct 130 ms 140088 KB Output is correct
46 Correct 124 ms 139980 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 123596 KB Output is correct
2 Correct 48 ms 123568 KB Output is correct
3 Correct 48 ms 123468 KB Output is correct
4 Correct 48 ms 123568 KB Output is correct
5 Correct 49 ms 123488 KB Output is correct
6 Correct 48 ms 123596 KB Output is correct
7 Correct 49 ms 123620 KB Output is correct
8 Correct 50 ms 123536 KB Output is correct
9 Correct 50 ms 123596 KB Output is correct
10 Correct 52 ms 123852 KB Output is correct
11 Correct 51 ms 123852 KB Output is correct
12 Correct 51 ms 123900 KB Output is correct
13 Correct 52 ms 123828 KB Output is correct
14 Correct 52 ms 123840 KB Output is correct
15 Correct 52 ms 123852 KB Output is correct
16 Correct 54 ms 124624 KB Output is correct
17 Correct 65 ms 128460 KB Output is correct
18 Correct 86 ms 135504 KB Output is correct
19 Correct 84 ms 137244 KB Output is correct
20 Correct 100 ms 137296 KB Output is correct
21 Correct 56 ms 126028 KB Output is correct
22 Correct 78 ms 135740 KB Output is correct
23 Correct 78 ms 134476 KB Output is correct
24 Correct 84 ms 136648 KB Output is correct
25 Correct 84 ms 137296 KB Output is correct
26 Correct 87 ms 137296 KB Output is correct
27 Correct 86 ms 137396 KB Output is correct
28 Correct 87 ms 137308 KB Output is correct
29 Correct 95 ms 137292 KB Output is correct
30 Correct 100 ms 137208 KB Output is correct
31 Correct 87 ms 137164 KB Output is correct
32 Correct 83 ms 137164 KB Output is correct
33 Correct 97 ms 137292 KB Output is correct
34 Correct 99 ms 137340 KB Output is correct
35 Correct 92 ms 134080 KB Output is correct
36 Correct 71 ms 131020 KB Output is correct
37 Correct 111 ms 137932 KB Output is correct
38 Correct 114 ms 138612 KB Output is correct
39 Correct 113 ms 138460 KB Output is correct
40 Correct 113 ms 138548 KB Output is correct
41 Correct 110 ms 138440 KB Output is correct
42 Correct 88 ms 137680 KB Output is correct
43 Correct 86 ms 137632 KB Output is correct
44 Correct 86 ms 137656 KB Output is correct
45 Correct 123 ms 139960 KB Output is correct
46 Correct 124 ms 140008 KB Output is correct
47 Correct 422 ms 214544 KB Output is correct
48 Runtime error 368 ms 262144 KB Execution killed with signal 9
49 Halted 0 ms 0 KB -