Submission #145660

#	Time	Username	Problem	Language	Result	Execution time	Memory
145660		Xylofo	Sky Walking (IOI19_walk)	C++17	0 / 100	867 ms	63928 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;


#define debug(...) //ignore


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 stALL= [&](){
    vector<map<ll,int>> Q;
    auto pcomp  = [&] (vi idx) {
      Q.emplace_back();
      int hh = 0;
      for(int i : idx) if(h[i] > hh) {
        hh = h[i];
        Q.back()[hh] = i;
      }
    };
    { vi ind; rep(i,s,n) ind.emplace_back(i); pcomp(ind); }
    { vi ind; for(int i = s; i >= 0; --i) ind.emplace_back(i); pcomp(ind); }
    { vi ind; rep(i,g,n) ind.emplace_back(i); pcomp(ind); }
    { vi ind; for(int i = g; i >= 0; --i) ind.emplace_back(i); pcomp(ind); }
    debug(Q);

    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};
        debug(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]);

      for(auto &q: Q) {
        auto it = q.lower_bound(y[i]);
        if(it == q.end()) continue;
        int j = it->second;
        debug("HEJ", i,j);
        if(l[i] <= j && j <= r[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;
  };

  return stALL();
}

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