oj.uz

Submission #899844

# Submission time Handle Problem Language Result Execution time Memory
899844 2024-01-07T07:21:54 Z rxlfd314 Sky Walking (IOI19_walk) C++17
0 / 100
 172 ms 52540 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
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) {
  const int N = size(X), M = size(L);
  vt<arl2> adj[N*16];
  vt<int> ys[N];
  map<ari2, int> cmp;
  int cnt = 0;
  auto get = [&](ari2 v) {
    return cmp.find(v) == end(cmp) ? cmp[v] = cnt++ : cmp[v];
  };
  FOR(i, 0, M-1) {
    ys[L[i]].push_back(Y[i]);
    FOR(j, L[i]+1, R[i]) {
      adj[get({X[j], Y[i]})].push_back({get({X[j-1], Y[i]}), X[j] - X[j-1]});
      adj[get({X[j-1], Y[i]})].push_back({get({X[j], Y[i]}), X[j] - X[j-1]});
      ys[j].push_back(Y[i]);
    }
  }
  FOR(i, 0, N-1) {
    ys[i].push_back(0);
    get({X[i], 0});
    sort(all(ys[i]));
    ys[i].erase(unique(all(ys[i])), end(ys[i]));
    FOR(j, 1, size(ys[i])-1) {
      if (ys[i][j] > H[i])
        break;
      adj[get({X[i], ys[i][j]})].push_back({get({X[i], ys[i][j-1]}), ys[i][j] - ys[i][j-1]});
      adj[get({X[i], ys[i][j-1]})].push_back({get({X[i], ys[i][j]}), ys[i][j] - ys[i][j-1]});
    }
  }
  priority_queue<arl2, vt<arl2>, greater<arl2>> pq;
  ll dst[cnt];
  memset(dst, 0x3f, sizeof(dst));
  pq.push({dst[get({X[S], 0})] = 0, get({X[S], 0})});
  while (size(pq)) {
    auto [d, i] = pq.top();
    pq.pop();
    if (d > dst[i])
      continue;
    for (auto &[j, v] : adj[i])
      if (d + v < dst[j])
        pq.push({dst[j] = d + v, j}); 
  }
  return dst[get({X[G], 0})] == 0x3f3f3f3f3f3f3f3f ? -1 : dst[get({X[G], 0})];
}

ll min_distance(vt<int> X, vt<int> H, vt<int> L, vt<int> R, vt<int> Y, int S, int G) {
	const int N = size(X), M = size(L);
  bool sub2 = true;
  FOR(i, 0, M-1)
    sub2 &= R[i] - L[i] < 15;
  if (sub2 || N < 51 && M < 51)
    return ST12(X, H, L, R, Y, S, 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:67:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   67 |   if (sub2 || N < 51 && M < 51)
      |               ~~~~~~~^~~~~~~~~
walk.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
   69 | }
      | ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 1 ms 604 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Runtime error 172 ms 52540 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 17948 KB Output is correct
2 Runtime error 34 ms 12116 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 17948 KB Output is correct
2 Runtime error 34 ms 12116 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 1 ms 604 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -