oj.uz

Submission #147995

# Submission time Handle Problem Language Result Execution time Memory
147995 2019-08-31T10:50:16 Z Xylofo Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 214688 KB 
#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 */
__gnu_pbds::gp_hash_table<ll,int> 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

walk.cpp: In member function 'void Graph::addUpDown(vi&, vi&)':
walk.cpp:72:16: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
       for(auto [hh, _] : perBuild[i]) {
                ^
walk.cpp:72:22: 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:103:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [y,w] : g[x]) {
              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1912 KB Output is correct
2 Correct 3 ms 1912 KB Output is correct
3 Correct 3 ms 1912 KB Output is correct
4 Correct 3 ms 1912 KB Output is correct
5 Correct 4 ms 1916 KB Output is correct
6 Correct 4 ms 1912 KB Output is correct
7 Correct 4 ms 1912 KB Output is correct
8 Correct 4 ms 1912 KB Output is correct
9 Correct 3 ms 1912 KB Output is correct
10 Correct 4 ms 1912 KB Output is correct
11 Correct 3 ms 1912 KB Output is correct
12 Correct 3 ms 1912 KB Output is correct
13 Correct 4 ms 1912 KB Output is correct
14 Correct 3 ms 1912 KB Output is correct
15 Correct 4 ms 1912 KB Output is correct
16 Correct 3 ms 1912 KB Output is correct
17 Correct 4 ms 1912 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1912 KB Output is correct
2 Correct 3 ms 1912 KB Output is correct
3 Correct 1365 ms 136604 KB Output is correct
4 Correct 1242 ms 141836 KB Output is correct
5 Correct 1092 ms 116024 KB Output is correct
6 Correct 935 ms 109748 KB Output is correct
7 Correct 871 ms 115992 KB Output is correct
8 Correct 1666 ms 147016 KB Output is correct
9 Correct 1077 ms 132456 KB Output is correct
10 Correct 1351 ms 147900 KB Output is correct
11 Correct 961 ms 110160 KB Output is correct
12 Correct 523 ms 69724 KB Output is correct
13 Correct 1330 ms 151996 KB Output is correct
14 Correct 803 ms 75464 KB Output is correct
15 Correct 901 ms 75996 KB Output is correct
16 Correct 750 ms 73336 KB Output is correct
17 Correct 930 ms 70916 KB Output is correct
18 Execution timed out 4035 ms 53132 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 25252 KB Output is correct
2 Correct 2013 ms 199360 KB Output is correct
3 Correct 2171 ms 205532 KB Output is correct
4 Correct 2212 ms 211836 KB Output is correct
5 Correct 2544 ms 214688 KB Output is correct
6 Correct 2279 ms 201716 KB Output is correct
7 Correct 950 ms 110180 KB Output is correct
8 Correct 530 ms 69616 KB Output is correct
9 Correct 2162 ms 165972 KB Output is correct
10 Execution timed out 4006 ms 53132 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 25252 KB Output is correct
2 Correct 2013 ms 199360 KB Output is correct
3 Correct 2171 ms 205532 KB Output is correct
4 Correct 2212 ms 211836 KB Output is correct
5 Correct 2544 ms 214688 KB Output is correct
6 Correct 2279 ms 201716 KB Output is correct
7 Correct 950 ms 110180 KB Output is correct
8 Correct 530 ms 69616 KB Output is correct
9 Correct 2162 ms 165972 KB Output is correct
10 Execution timed out 4006 ms 53132 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1912 KB Output is correct
2 Correct 3 ms 1912 KB Output is correct
3 Correct 3 ms 1912 KB Output is correct
4 Correct 3 ms 1912 KB Output is correct
5 Correct 4 ms 1916 KB Output is correct
6 Correct 4 ms 1912 KB Output is correct
7 Correct 4 ms 1912 KB Output is correct
8 Correct 4 ms 1912 KB Output is correct
9 Correct 3 ms 1912 KB Output is correct
10 Correct 4 ms 1912 KB Output is correct
11 Correct 3 ms 1912 KB Output is correct
12 Correct 3 ms 1912 KB Output is correct
13 Correct 4 ms 1912 KB Output is correct
14 Correct 3 ms 1912 KB Output is correct
15 Correct 4 ms 1912 KB Output is correct
16 Correct 3 ms 1912 KB Output is correct
17 Correct 4 ms 1912 KB Output is correct
18 Correct 3 ms 1912 KB Output is correct
19 Correct 3 ms 1912 KB Output is correct
20 Correct 1365 ms 136604 KB Output is correct
21 Correct 1242 ms 141836 KB Output is correct
22 Correct 1092 ms 116024 KB Output is correct
23 Correct 935 ms 109748 KB Output is correct
24 Correct 871 ms 115992 KB Output is correct
25 Correct 1666 ms 147016 KB Output is correct
26 Correct 1077 ms 132456 KB Output is correct
27 Correct 1351 ms 147900 KB Output is correct
28 Correct 961 ms 110160 KB Output is correct
29 Correct 523 ms 69724 KB Output is correct
30 Correct 1330 ms 151996 KB Output is correct
31 Correct 803 ms 75464 KB Output is correct
32 Correct 901 ms 75996 KB Output is correct
33 Correct 750 ms 73336 KB Output is correct
34 Correct 930 ms 70916 KB Output is correct
35 Execution timed out 4035 ms 53132 KB Time limit exceeded
36 Halted 0 ms 0 KB -