Submission #899835

#	Time	Username	Problem	Language	Result	Execution time	Memory
899835		rxlfd314	Sky Walking (IOI19_walk)	C++17	10 / 100	4054 ms	1048576 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 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);
  map<ari2, vt<ari2>> adj;
  vt<int> ys[N];
  FOR(i, 0, M-1) {
    ys[L[i]].push_back(Y[i]);
    FOR(j, L[i]+1, R[i]) {
      adj[{X[j], Y[i]}].push_back({X[j-1], Y[i]});
      adj[{X[j-1], Y[i]}].push_back({X[j], Y[i]});
      ys[j].push_back(Y[i]);
    }
  }
  FOR(i, 0, N-1) {
    ys[i].push_back(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[{X[i], ys[i][j]}].push_back({X[i], ys[i][j-1]});
      adj[{X[i], ys[i][j-1]}].push_back({X[i], ys[i][j]});
    }
  }
  map<ari2, ll> dst;
  priority_queue<arl3, vt<arl3>, greater<arl3>> pq;
  pq.push({dst[{X[S], 0}] = 0, X[S], 0});
  while (size(pq)) {
    auto [d, x, y] = pq.top();
    pq.pop();
    if (d > dst[{x, y}])
      continue;
    #ifdef DEBUG
    cout << "at " << x << ' ' << y << " with dist of " << d << '\n';
    #endif
    for (auto &[a, b] : adj[{x, y}])
      if (dst.find({a, b}) == end(dst) || d + abs(x - a) + abs(y - b) < dst[{a, b}])
        pq.push({dst[{a, b}] = d + abs(x - a) + abs(y - b), a, b});
  }
  return dst.find({X[G], 0}) == end(dst) ? -1 : dst[{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 (stderr)

walk.cpp: In function 'll ST12(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:45:18: warning: narrowing conversion of 'x' from 'std::tuple_element<1, std::array<long long int, 3> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
   45 |     if (d > dst[{x, y}])
      |                  ^
walk.cpp:45:21: warning: narrowing conversion of 'y' from 'std::tuple_element<2, std::array<long long int, 3> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
   45 |     if (d > dst[{x, y}])
      |                     ^
walk.cpp:50:30: warning: narrowing conversion of 'x' from 'std::tuple_element<1, std::array<long long int, 3> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
   50 |     for (auto &[a, b] : adj[{x, y}])
      |                              ^
walk.cpp:50:33: warning: narrowing conversion of 'y' from 'std::tuple_element<2, std::array<long long int, 3> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
   50 |     for (auto &[a, b] : adj[{x, y}])
      |                                 ^
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:62:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   62 |   if (sub2 || N < 51 && M < 51)
      |               ~~~~~~~^~~~~~~~~
walk.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
   64 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43