oj.uz

답안 #839251

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
839251 2023-08-29T11:03:55 Z tch1cherin Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 281 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 30000;
const int C = 200;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 164684 KB Output is correct
2 Correct 69 ms 164564 KB Output is correct
3 Correct 67 ms 164688 KB Output is correct
4 Correct 69 ms 164684 KB Output is correct
5 Correct 63 ms 164684 KB Output is correct
6 Correct 70 ms 164696 KB Output is correct
7 Correct 66 ms 164696 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 164684 KB Output is correct
2 Correct 66 ms 164580 KB Output is correct
3 Correct 66 ms 164668 KB Output is correct
4 Correct 71 ms 164688 KB Output is correct
5 Correct 68 ms 164812 KB Output is correct
6 Correct 66 ms 164648 KB Output is correct
7 Correct 76 ms 164664 KB Output is correct
8 Correct 68 ms 164652 KB Output is correct
9 Correct 69 ms 164780 KB Output is correct
10 Correct 67 ms 164928 KB Output is correct
11 Correct 71 ms 164920 KB Output is correct
12 Correct 70 ms 164888 KB Output is correct
13 Correct 68 ms 165000 KB Output is correct
14 Correct 67 ms 164952 KB Output is correct
15 Correct 67 ms 165052 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 164604 KB Output is correct
2 Correct 65 ms 164632 KB Output is correct
3 Correct 64 ms 164624 KB Output is correct
4 Correct 66 ms 164632 KB Output is correct
5 Correct 64 ms 164684 KB Output is correct
6 Correct 65 ms 164628 KB Output is correct
7 Correct 64 ms 164644 KB Output is correct
8 Correct 64 ms 164724 KB Output is correct
9 Correct 65 ms 164784 KB Output is correct
10 Correct 68 ms 165016 KB Output is correct
11 Correct 66 ms 165004 KB Output is correct
12 Correct 68 ms 164920 KB Output is correct
13 Correct 66 ms 164996 KB Output is correct
14 Correct 68 ms 165032 KB Output is correct
15 Correct 66 ms 164984 KB Output is correct
16 Correct 68 ms 165752 KB Output is correct
17 Correct 83 ms 171084 KB Output is correct
18 Correct 101 ms 180328 KB Output is correct
19 Correct 106 ms 182764 KB Output is correct
20 Correct 108 ms 182768 KB Output is correct
21 Correct 70 ms 167824 KB Output is correct
22 Correct 108 ms 180752 KB Output is correct
23 Correct 100 ms 179032 KB Output is correct
24 Correct 106 ms 181836 KB Output is correct
25 Correct 107 ms 182852 KB Output is correct
26 Correct 108 ms 182692 KB Output is correct
27 Correct 113 ms 182816 KB Output is correct
28 Correct 109 ms 182844 KB Output is correct
29 Correct 114 ms 182800 KB Output is correct
30 Correct 116 ms 182760 KB Output is correct
31 Correct 112 ms 182792 KB Output is correct
32 Correct 119 ms 182816 KB Output is correct
33 Correct 120 ms 182868 KB Output is correct
34 Correct 123 ms 182760 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 164580 KB Output is correct
2 Correct 67 ms 164640 KB Output is correct
3 Correct 67 ms 164692 KB Output is correct
4 Correct 68 ms 164648 KB Output is correct
5 Correct 70 ms 164624 KB Output is correct
6 Correct 67 ms 164700 KB Output is correct
7 Correct 65 ms 164700 KB Output is correct
8 Correct 78 ms 164688 KB Output is correct
9 Correct 71 ms 164712 KB Output is correct
10 Correct 71 ms 164936 KB Output is correct
11 Correct 68 ms 164916 KB Output is correct
12 Correct 66 ms 164888 KB Output is correct
13 Correct 68 ms 165000 KB Output is correct
14 Correct 68 ms 164940 KB Output is correct
15 Correct 69 ms 164956 KB Output is correct
16 Correct 72 ms 165736 KB Output is correct
17 Correct 83 ms 171044 KB Output is correct
18 Correct 110 ms 180416 KB Output is correct
19 Correct 117 ms 182796 KB Output is correct
20 Correct 106 ms 182848 KB Output is correct
21 Correct 76 ms 167688 KB Output is correct
22 Correct 104 ms 180636 KB Output is correct
23 Correct 98 ms 179056 KB Output is correct
24 Correct 107 ms 181820 KB Output is correct
25 Correct 130 ms 182780 KB Output is correct
26 Correct 109 ms 182808 KB Output is correct
27 Correct 107 ms 182812 KB Output is correct
28 Correct 109 ms 182828 KB Output is correct
29 Correct 113 ms 182768 KB Output is correct
30 Correct 107 ms 182692 KB Output is correct
31 Correct 128 ms 182792 KB Output is correct
32 Correct 112 ms 182792 KB Output is correct
33 Correct 120 ms 182868 KB Output is correct
34 Correct 116 ms 182796 KB Output is correct
35 Correct 112 ms 178552 KB Output is correct
36 Correct 91 ms 174416 KB Output is correct
37 Correct 141 ms 183404 KB Output is correct
38 Correct 135 ms 184224 KB Output is correct
39 Correct 172 ms 184156 KB Output is correct
40 Correct 147 ms 184244 KB Output is correct
41 Correct 139 ms 184244 KB Output is correct
42 Correct 110 ms 183448 KB Output is correct
43 Correct 110 ms 183368 KB Output is correct
44 Correct 109 ms 183452 KB Output is correct
45 Correct 166 ms 184912 KB Output is correct
46 Correct 163 ms 184868 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 164636 KB Output is correct
2 Correct 74 ms 164604 KB Output is correct
3 Correct 65 ms 164620 KB Output is correct
4 Correct 67 ms 164588 KB Output is correct
5 Correct 64 ms 164628 KB Output is correct
6 Correct 66 ms 164684 KB Output is correct
7 Correct 64 ms 164596 KB Output is correct
8 Correct 67 ms 164688 KB Output is correct
9 Correct 67 ms 164704 KB Output is correct
10 Correct 66 ms 164976 KB Output is correct
11 Correct 66 ms 165032 KB Output is correct
12 Correct 66 ms 164992 KB Output is correct
13 Correct 67 ms 164940 KB Output is correct
14 Correct 66 ms 164980 KB Output is correct
15 Correct 66 ms 164972 KB Output is correct
16 Correct 71 ms 165688 KB Output is correct
17 Correct 87 ms 171036 KB Output is correct
18 Correct 101 ms 180364 KB Output is correct
19 Correct 108 ms 182676 KB Output is correct
20 Correct 111 ms 182832 KB Output is correct
21 Correct 75 ms 167660 KB Output is correct
22 Correct 117 ms 180816 KB Output is correct
23 Correct 104 ms 179004 KB Output is correct
24 Correct 112 ms 181884 KB Output is correct
25 Correct 111 ms 182852 KB Output is correct
26 Correct 109 ms 182732 KB Output is correct
27 Correct 115 ms 182812 KB Output is correct
28 Correct 117 ms 182804 KB Output is correct
29 Correct 117 ms 182752 KB Output is correct
30 Correct 112 ms 182684 KB Output is correct
31 Correct 114 ms 182712 KB Output is correct
32 Correct 119 ms 182788 KB Output is correct
33 Correct 126 ms 182740 KB Output is correct
34 Correct 132 ms 182840 KB Output is correct
35 Correct 113 ms 178560 KB Output is correct
36 Correct 93 ms 174384 KB Output is correct
37 Correct 157 ms 183404 KB Output is correct
38 Correct 147 ms 184216 KB Output is correct
39 Correct 144 ms 184224 KB Output is correct
40 Correct 147 ms 184224 KB Output is correct
41 Correct 151 ms 184364 KB Output is correct
42 Correct 111 ms 183412 KB Output is correct
43 Correct 111 ms 183376 KB Output is correct
44 Correct 109 ms 183372 KB Output is correct
45 Correct 171 ms 184996 KB Output is correct
46 Correct 162 ms 184892 KB Output is correct
47 Runtime error 281 ms 262144 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -