oj.uz

답안 #839248

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

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 * 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 106 ms 246976 KB Output is correct
2 Correct 97 ms 246808 KB Output is correct
3 Correct 99 ms 246848 KB Output is correct
4 Correct 100 ms 246880 KB Output is correct
5 Correct 102 ms 246924 KB Output is correct
6 Correct 99 ms 246840 KB Output is correct
7 Correct 98 ms 246776 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 246820 KB Output is correct
2 Correct 99 ms 246852 KB Output is correct
3 Correct 102 ms 246836 KB Output is correct
4 Correct 105 ms 246832 KB Output is correct
5 Correct 101 ms 247020 KB Output is correct
6 Correct 99 ms 246876 KB Output is correct
7 Correct 98 ms 246800 KB Output is correct
8 Correct 102 ms 246964 KB Output is correct
9 Correct 99 ms 246860 KB Output is correct
10 Correct 100 ms 247136 KB Output is correct
11 Correct 102 ms 247104 KB Output is correct
12 Correct 102 ms 247140 KB Output is correct
13 Correct 104 ms 247200 KB Output is correct
14 Correct 98 ms 247188 KB Output is correct
15 Correct 100 ms 247160 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 246768 KB Output is correct
2 Correct 96 ms 246788 KB Output is correct
3 Correct 103 ms 246836 KB Output is correct
4 Correct 96 ms 246844 KB Output is correct
5 Correct 95 ms 246848 KB Output is correct
6 Correct 97 ms 246852 KB Output is correct
7 Correct 95 ms 246856 KB Output is correct
8 Correct 98 ms 246920 KB Output is correct
9 Correct 102 ms 246900 KB Output is correct
10 Correct 100 ms 247072 KB Output is correct
11 Correct 97 ms 247164 KB Output is correct
12 Correct 97 ms 247156 KB Output is correct
13 Correct 103 ms 247096 KB Output is correct
14 Correct 99 ms 247108 KB Output is correct
15 Correct 98 ms 247116 KB Output is correct
16 Correct 100 ms 247988 KB Output is correct
17 Correct 119 ms 255896 KB Output is correct
18 Runtime error 126 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 246872 KB Output is correct
2 Correct 95 ms 246888 KB Output is correct
3 Correct 99 ms 246764 KB Output is correct
4 Correct 98 ms 246884 KB Output is correct
5 Correct 104 ms 246880 KB Output is correct
6 Correct 95 ms 246884 KB Output is correct
7 Correct 95 ms 246808 KB Output is correct
8 Correct 95 ms 246832 KB Output is correct
9 Correct 98 ms 246972 KB Output is correct
10 Correct 103 ms 247268 KB Output is correct
11 Correct 98 ms 247232 KB Output is correct
12 Correct 97 ms 247080 KB Output is correct
13 Correct 99 ms 247192 KB Output is correct
14 Correct 98 ms 247244 KB Output is correct
15 Correct 103 ms 247212 KB Output is correct
16 Correct 100 ms 247936 KB Output is correct
17 Correct 120 ms 255864 KB Output is correct
18 Runtime error 128 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 246884 KB Output is correct
2 Correct 97 ms 246824 KB Output is correct
3 Correct 95 ms 246880 KB Output is correct
4 Correct 99 ms 246764 KB Output is correct
5 Correct 95 ms 246816 KB Output is correct
6 Correct 98 ms 246880 KB Output is correct
7 Correct 98 ms 246936 KB Output is correct
8 Correct 96 ms 246880 KB Output is correct
9 Correct 99 ms 246860 KB Output is correct
10 Correct 100 ms 247096 KB Output is correct
11 Correct 107 ms 247216 KB Output is correct
12 Correct 107 ms 247132 KB Output is correct
13 Correct 100 ms 247156 KB Output is correct
14 Correct 99 ms 247232 KB Output is correct
15 Correct 101 ms 247224 KB Output is correct
16 Correct 103 ms 247912 KB Output is correct
17 Correct 125 ms 255948 KB Output is correct
18 Runtime error 122 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -