Submission #147992

#	Time	Username	Problem	Language	Result	Execution time	Memory
147992		Xylofo	Sky Walking (IOI19_walk)	C++14	100 / 100	3425 ms	263292 KiB

walk

    #pragma GCC optimize("Ofast")
     
    #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
     
    #include <bits/extc++.h> /** keep-include */
    struct chash {
      const uint64_t C = ll(2e18 * M_PI) + 71; // large odd number
      ll operator()(ll x) const { return __builtin_bswap64(x*C); }
    };
    __gnu_pbds::gp_hash_table<ll,int,chash> V({},{},{},{},{1<<16});
     
    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.find(p) == V.end()) { 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);
        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:76:20: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
           for(auto [hh, _] : perBuild[i]) {
                    ^
walk.cpp:76:26: warning: unused variable '_' [-Wunused-variable]
           for(auto [hh, _] : perBuild[i]) {
                          ^
walk.cpp: In function 'auto dijkstra(int, std::vector<std::vector<std::pair<int, T> > >&)':
walk.cpp:107:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         for(auto [y,w] : g[x]) {
                  ^

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