Submission #147959

#	Time	Username	Problem	Language	Result	Execution time	Memory
147959		Xylofo	Sky Walking (IOI19_walk)	C++17	43 / 100	2927 ms	195380 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

struct Graph {
  int n,m;
  vi x,y,h;
  unordered_map<ll, int> V; // verts, indexed by 2e9*x+h
  vector<vector<pair<int,ll>>> E; // adj-list
  vector<map<ll,int> > perBuild, perWalk;

  Graph(vi x, vi y, vi h)
    : n(sz(x)), m(sz(y)), x(x), y(y), h(h), perBuild(n), perWalk(m) {}

  int at(ll x, ll h) { // return vertex handle of (x,h)
    auto p = x*(ll(2e9))+ h;
    if (!V.count(p)) { V[p] = sz(E); E.eb(); }
    return V[p];
  }

  void add(int build, int walk) { // pt (x[build], y[walk]) is important
    ll X = x[build], Y = y[walk];
    assert(h[build] >= Y);
    int q = at(X, Y);
    perBuild[build][Y] = q;
    perWalk[walk][X] = q;
  }

  void edge(int a, int b, ll c){ // create edge
    E[a].eb(b,c);
    E[b].eb(a,c);
  }

  void edges(map<ll,int>& vert) { // create edges on line
    vector<pair<ll,int> > vv(all(vert));
    rep(i,1,sz(vv))
      edge(vv[i-1].second, vv[i].second, vv[i].first-vv[i-1].first);
  }

  void addUpDown(vi l, vi r) { // add things directely above/below points added.
    vector<vi> start(n), end(n);
    rep(i,0,m) start[l[i]].eb(i), end[r[i]].eb(i);
    map<ll,int> active;
    rep(i,0,n) {
      trav(w,end[i]) active.erase(y[w]);
      trav(w,start[i]) active[y[w]] = w;
      vi toAdd;
      for(auto [hh, _] : perBuild[i]) {
        auto it = active.upper_bound(hh);
        auto maybeAdd = [&](int w) { if (y[w] <= h[i]) toAdd.eb(w); };
        if(it != active.end()) maybeAdd(it->second);
        it = active.lower_bound(hh);
        if(it != active.begin()) maybeAdd((--it)->second);
      }
      trav(w, toAdd) add(i,w);
    }
  }

  void build(){
    trav(v, perBuild) edges(v);
    trav(v, perWalk) edges(v);
  }
};

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 dist;
}



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.eb();
      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.eb(i); pcomp(ind); }
    { vi ind; for(int i = s; i >= 0; --i) ind.eb(i); pcomp(ind); }
    { vi ind; rep(i,g,n) ind.eb(i); pcomp(ind); }
    { vi ind; for(int i = g; i >= 0; --i) ind.eb(i); pcomp(ind); }
    //debug(Q);

    Graph G(x,y,h);

    int S = G.perBuild[s][0] = G.at(x[s], 0);
    int T = G.perBuild[g][0] = G.at(x[g], 0);

    debug("added", s, g);

    rep(i,0,m) {
      // add endpoints
      G.add(l[i],i);
      G.add(r[i],i);

      // add closest to s and g in each direction.
      // for(auto &q: Q) {
      //   auto it = q.lower_bound(y[i]);
      //   if(it == q.end()) continue;
      //   int j = it->second;
      //   if(l[i] <= j && j <= r[i]) G.add(j, i);
      // }
    }

    debug("added pts 1");
    debug(sz(G.E));

    G.addUpDown(l,r);

    debug("added pts 2");
    debug(sz(G.E));

    G.build();

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

  return stALL();
}

Compilation message (stderr)

walk.cpp: In member function 'void Graph::addUpDown(vi, vi)':
walk.cpp:67:22: warning: unused variable '_' [-Wunused-variable]
       for(auto [hh, _] : perBuild[i]) {
                      ^

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