oj.uz

답안 #899861

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899861 2024-01-07T07:42:55 Z rxlfd314 Sky Walking (IOI19_walk) C++17
0 / 100
 16 ms 3148 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

ll ST12(vt<int> X, vt<int> H, vt<int> L, vt<int> R, vt<int> Y, int S, int G, int LEN) {
  const int N = size(X), M = size(L);
  vt<ari3> points;
  FOR(i, 0, M-1)
    FOR(j, L[i], R[i])
      points.push_back({j, Y[i], i});
  FOR(i, 0, N-1)
    points.push_back({i, 0, -1});
  
  sort(all(points));
  points.erase(unique(all(points)), end(points));
  
  int prv[M];
  memset(prv, -1, sizeof(prv));
  
  vt<ari2> adj[size(points)];
  priority_queue<arl2, vt<arl2>, greater<arl2>> pq;
  ll dst[size(points)];
  memset(dst, 0x3f, sizeof(dst));
  FOR(i, 0, size(points)-1) {
    if (i && points[i][0] == points[i-1][0] && points[i][1] <= H[points[i][0]]) {
      adj[i-1].push_back({i, points[i][1] - points[i-1][1]});
      adj[i].push_back({i-1, points[i][1] - points[i-1][1]});
    }
    if (~points[i][2] && ~prv[points[i][2]]) {
      adj[i].push_back({prv[points[i][2]], X[points[i][0]] - X[points[prv[points[i][2]]][0]]});
      adj[prv[points[i][2]]].push_back({i, X[points[i][0]] - X[points[prv[points[i][2]]][0]]});
    }
    if (~points[i][2])
      prv[points[i][2]] = i;
    if (points[i][0] == S && !points[i][1])
      pq.push({dst[i] = 0, i});
  }
  
  while (size(pq)) {
    auto [d, i] = pq.top();
    pq.pop();
    if (points[i][0] == G && !points[i][1])
      return d;
    if (d > dst[i])
      continue;
    #ifdef DEBUG
    cout << "at " << X[points[i][0]] << ' ' << points[i][1] << " with dist of " << d << '\n';
    #endif
    for (auto &[j, v] : adj[i])
      if (d + v < dst[j])
        pq.push({dst[j] = d + v, j});
  }
  
  return -1;
}

ll min_distance(vt<int> X, vt<int> H, vt<int> L, vt<int> R, vt<int> Y, int S, int G) {
}

Compilation message

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:71:1: warning: no return statement in function returning non-void [-Wreturn-type]
   71 | }
      | ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 3148 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 3148 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -