Submission #145658

#	Time	Username	Problem	Language	Result	Execution time	Memory
145658		Xylofo	Sky Walking (IOI19_walk)	C++17	43 / 100	4033 ms	296692 KiB

walk

#include "walk.h"

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define eb emplace_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const ll INF =1e18;


#ifdef LOCAL
#include "../../../../../MixedFunc/pretty_debug.h"
#else
#define debug(...) //ignore
#endif


template<class T>
auto dijkstra(int source, vector<vector<pair<int, T>>> &g) {
  int n = sz(g);
  vector<T> dist(n, numeric_limits<T>::max());
  vector<pair<int,T> > dad(n, {-1, 0});
  priority_queue<pair<T,int> > pq;
  dist[source] = 0;
  pq.emplace(0,source);
  while(!pq.empty()) {
    T d; int x;
    tie(d,x) = pq.top();
    d = -d;
    pq.pop();
    if(d > dist[x]) continue;
    for(auto [y,w] : g[x]) {
      if(dist[y] > d + w) {
        dist[y] = d + w;
        dad[y] = {x, w};
        pq.emplace(-dist[y], y);
      }
    }
  }
  return pair{dist, dad};
}



ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
  int n = sz(x), m = sz(l);
  debug(n,m);

  auto st12 = [&](){
    map<ll, map<ll, int> > V;
    map<int, pair<ll,ll>> iV;
    vector<vector<pair<int,ll>>> E;
    auto at = [&](int i, int h) {
      if (!V[x[i]].count(h)) {
        V[x[i]][h] = sz(E);
        iV[sz(E)] = {x[i],h};
        E.emplace_back();
      }
      return V[x[i]][h];
    };
    auto edge = [&](int a, int b, ll c) {
      E[a].emplace_back(b,c);
      E[b].emplace_back(a,c);
    };
    auto edges = [&](map<ll,int> vert) {
      pair<ll,int> a = *vert.begin();
      vert.erase(vert.begin());
      for(auto b : vert) {
        edge(a.second, b.second, b.first-a.first);
        a = b;
      }
    };

    at(s,0);
    at(g,0);

    rep(i,0,m) {
      l[i], r[i], y[i];
      map<ll, int> vert;
      vert[x[l[i]]] = at(l[i], y[i]);
      vert[x[r[i]]] = at(r[i], y[i]);

      // temporary
      rep(j,l[i]+1, r[i]) if(h[j] >= y[i])
        vert[x[j]] = at(j, y[i]);

      edges(vert);
    }

    for(auto v: V) edges(v.second);
    debug(sz(E))

    auto[dist, dad] = dijkstra(at(s,0),E);
    for(int q = at(g,0); dad[q].first != -1; q = dad[q].first) {
      debug(iV[q]);
    }
    ll ans = dist[at(g, 0)];
    if (ans >= INF) ans = -1;
    return ans;
  };

  auto st34 = [&](){
    vector<vi> start(n), end(n);
    rep(i,0,m) {
      start[l[i]].eb(y[i]);
      end[r[i]].eb(y[i]);
    }
    start[n-1].eb(0);
    end[0].eb(0);
    // cost[h] = get to dp[h]
    map<int, ll> cost;
    map<int, ll> cnt;
    cost[0] = 0;
    cnt[0] = 1;
    debug(n);
    rep(i,0,n) {
      debug(i, cost);
      for(int H : start[i]) {
        if(cnt[H]++ == 0) {
          debug("add", H);
          ll c = INF;
          auto C = [&](auto p) { return p.second + abs(p.first - H); };
          auto it = cost.lower_bound(H);
          if(it != cost.end()) c = min(c, C(*it));
          if(it != cost.begin()) c = min(c, C(*--it));
          cost[H] = c;
        }
      }
      for(int H : end[i]) {
        if(--cnt[H] == 0) {
          debug("rem", H);
          cost.erase(H);
        }
      }
    }
    debug(cost)
      debug(x[n-1] - x[0]);
    ll ans = cost[0] + x[n-1]-x[0];
    if (ans >= INF) ans = -1;
    return ans;
  };

  if (s == 0 && g == n-1) return st34();
  else return st12();
}

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