oj.uz

Submission #147959

# Submission time Handle Problem Language Result Execution time Memory
147959 2019-08-31T10:15:09 Z Xylofo Sky Walking (IOI19_walk) C++17
43 / 100
 2927 ms 195380 KB 
#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

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.0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 1682 ms 130620 KB Output is correct
4 Correct 1598 ms 137672 KB Output is correct
5 Correct 1094 ms 108600 KB Output is correct
6 Correct 1004 ms 101216 KB Output is correct
7 Correct 1270 ms 108704 KB Output is correct
8 Correct 1974 ms 145820 KB Output is correct
9 Correct 1421 ms 127036 KB Output is correct
10 Incorrect 1733 ms 148232 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 25468 KB Output is correct
2 Correct 2423 ms 176788 KB Output is correct
3 Correct 2668 ms 184204 KB Output is correct
4 Correct 2905 ms 192348 KB Output is correct
5 Correct 2927 ms 195376 KB Output is correct
6 Correct 2645 ms 180752 KB Output is correct
7 Correct 1117 ms 101516 KB Output is correct
8 Correct 732 ms 68652 KB Output is correct
9 Correct 2447 ms 168144 KB Output is correct
10 Correct 968 ms 92968 KB Output is correct
11 Correct 21 ms 7332 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 25468 KB Output is correct
2 Correct 2423 ms 176788 KB Output is correct
3 Correct 2668 ms 184204 KB Output is correct
4 Correct 2905 ms 192348 KB Output is correct
5 Correct 2927 ms 195376 KB Output is correct
6 Correct 2645 ms 180752 KB Output is correct
7 Correct 1117 ms 101516 KB Output is correct
8 Correct 732 ms 68652 KB Output is correct
9 Correct 2447 ms 168144 KB Output is correct
10 Correct 968 ms 92968 KB Output is correct
11 Correct 21 ms 7332 KB Output is correct
12 Correct 2657 ms 183824 KB Output is correct
13 Correct 2668 ms 191544 KB Output is correct
14 Correct 2909 ms 195380 KB Output is correct
15 Correct 1922 ms 151916 KB Output is correct
16 Correct 1930 ms 155200 KB Output is correct
17 Correct 2282 ms 191084 KB Output is correct
18 Correct 1883 ms 151740 KB Output is correct
19 Correct 2007 ms 154980 KB Output is correct
20 Correct 1238 ms 99188 KB Output is correct
21 Correct 55 ms 15072 KB Output is correct
22 Correct 1613 ms 147604 KB Output is correct
23 Correct 1357 ms 132488 KB Output is correct
24 Correct 886 ms 88920 KB Output is correct
25 Correct 1252 ms 122104 KB Output is correct
26 Correct 665 ms 66000 KB Output is correct
27 Correct 2885 ms 194924 KB Output is correct
28 Correct 2165 ms 188692 KB Output is correct
29 Correct 2682 ms 180672 KB Output is correct
30 Correct 1138 ms 101096 KB Output is correct
31 Correct 2483 ms 168072 KB Output is correct
32 Correct 943 ms 81104 KB Output is correct
33 Correct 908 ms 80864 KB Output is correct
34 Correct 1006 ms 89700 KB Output is correct
35 Correct 1102 ms 98676 KB Output is correct
36 Correct 853 ms 81316 KB Output is correct
37 Correct 668 ms 67732 KB Output is correct
38 Correct 603 ms 69032 KB Output is correct
39 Correct 1084 ms 85916 KB Output is correct
40 Correct 661 ms 68940 KB Output is correct
41 Correct 688 ms 68616 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 1682 ms 130620 KB Output is correct
21 Correct 1598 ms 137672 KB Output is correct
22 Correct 1094 ms 108600 KB Output is correct
23 Correct 1004 ms 101216 KB Output is correct
24 Correct 1270 ms 108704 KB Output is correct
25 Correct 1974 ms 145820 KB Output is correct
26 Correct 1421 ms 127036 KB Output is correct
27 Incorrect 1733 ms 148232 KB Output isn't correct
28 Halted 0 ms 0 KB -