oj.uz

Submission #147977

# Submission time Handle Problem Language Result Execution time Memory
147977 2019-08-31T10:26:21 Z Xylofo Sky Walking (IOI19_walk) C++14
57 / 100
 4000 ms 241864 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] && y[w] != hh) toAdd.eb(w); };
        if(it != active.end()) maybeAdd(it->second);
        if(it != active.begin()) maybeAdd((--it)->second);
        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:16: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
       for(auto [hh, _] : perBuild[i]) {
                ^
walk.cpp:67: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:98: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 2 ms 256 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 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 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
14.0 / 14.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 1894 ms 141452 KB Output is correct
4 Correct 1811 ms 145740 KB Output is correct
5 Correct 1172 ms 111352 KB Output is correct
6 Correct 1167 ms 102896 KB Output is correct
7 Correct 1119 ms 111556 KB Output is correct
8 Correct 2043 ms 156440 KB Output is correct
9 Correct 1386 ms 130988 KB Output is correct
10 Correct 1845 ms 155960 KB Output is correct
11 Correct 1216 ms 101300 KB Output is correct
12 Correct 707 ms 64732 KB Output is correct
13 Correct 1907 ms 163152 KB Output is correct
14 Correct 953 ms 71216 KB Output is correct
15 Correct 852 ms 71228 KB Output is correct
16 Correct 728 ms 69116 KB Output is correct
17 Correct 689 ms 66456 KB Output is correct
18 Correct 1040 ms 75804 KB Output is correct
19 Correct 19 ms 3896 KB Output is correct
20 Correct 255 ms 35648 KB Output is correct
21 Correct 628 ms 64924 KB Output is correct
22 Correct 586 ms 65912 KB Output is correct
23 Correct 1079 ms 83040 KB Output is correct
24 Correct 678 ms 65808 KB Output is correct
25 Correct 689 ms 65896 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 24780 KB Output is correct
2 Correct 2754 ms 199256 KB Output is correct
3 Correct 2973 ms 209576 KB Output is correct
4 Correct 2983 ms 216216 KB Output is correct
5 Correct 3281 ms 219112 KB Output is correct
6 Correct 3035 ms 197696 KB Output is correct
7 Correct 1354 ms 112276 KB Output is correct
8 Correct 714 ms 64612 KB Output is correct
9 Correct 2604 ms 178224 KB Output is correct
10 Correct 964 ms 89544 KB Output is correct
11 Correct 21 ms 6564 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 24780 KB Output is correct
2 Correct 2754 ms 199256 KB Output is correct
3 Correct 2973 ms 209576 KB Output is correct
4 Correct 2983 ms 216216 KB Output is correct
5 Correct 3281 ms 219112 KB Output is correct
6 Correct 3035 ms 197696 KB Output is correct
7 Correct 1354 ms 112276 KB Output is correct
8 Correct 714 ms 64612 KB Output is correct
9 Correct 2604 ms 178224 KB Output is correct
10 Correct 964 ms 89544 KB Output is correct
11 Correct 21 ms 6564 KB Output is correct
12 Correct 3047 ms 208888 KB Output is correct
13 Correct 2762 ms 215140 KB Output is correct
14 Correct 3254 ms 219056 KB Output is correct
15 Correct 2092 ms 166824 KB Output is correct
16 Correct 2244 ms 169940 KB Output is correct
17 Correct 2735 ms 214364 KB Output is correct
18 Correct 2198 ms 167064 KB Output is correct
19 Correct 2252 ms 169500 KB Output is correct
20 Correct 1321 ms 109308 KB Output is correct
21 Correct 57 ms 13152 KB Output is correct
22 Correct 1861 ms 161772 KB Output is correct
23 Correct 1737 ms 145692 KB Output is correct
24 Correct 995 ms 88404 KB Output is correct
25 Correct 1314 ms 127804 KB Output is correct
26 Correct 639 ms 62216 KB Output is correct
27 Correct 3256 ms 218580 KB Output is correct
28 Correct 2431 ms 211524 KB Output is correct
29 Correct 2979 ms 197548 KB Output is correct
30 Correct 1306 ms 111656 KB Output is correct
31 Correct 2658 ms 178096 KB Output is correct
32 Correct 858 ms 77996 KB Output is correct
33 Correct 831 ms 77532 KB Output is correct
34 Correct 1006 ms 86416 KB Output is correct
35 Correct 1174 ms 101076 KB Output is correct
36 Correct 860 ms 79296 KB Output is correct
37 Correct 663 ms 64952 KB Output is correct
38 Correct 646 ms 65892 KB Output is correct
39 Correct 1167 ms 83116 KB Output is correct
40 Correct 699 ms 65944 KB Output is correct
41 Correct 782 ms 65852 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 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 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 1894 ms 141452 KB Output is correct
21 Correct 1811 ms 145740 KB Output is correct
22 Correct 1172 ms 111352 KB Output is correct
23 Correct 1167 ms 102896 KB Output is correct
24 Correct 1119 ms 111556 KB Output is correct
25 Correct 2043 ms 156440 KB Output is correct
26 Correct 1386 ms 130988 KB Output is correct
27 Correct 1845 ms 155960 KB Output is correct
28 Correct 1216 ms 101300 KB Output is correct
29 Correct 707 ms 64732 KB Output is correct
30 Correct 1907 ms 163152 KB Output is correct
31 Correct 953 ms 71216 KB Output is correct
32 Correct 852 ms 71228 KB Output is correct
33 Correct 728 ms 69116 KB Output is correct
34 Correct 689 ms 66456 KB Output is correct
35 Correct 1040 ms 75804 KB Output is correct
36 Correct 19 ms 3896 KB Output is correct
37 Correct 255 ms 35648 KB Output is correct
38 Correct 628 ms 64924 KB Output is correct
39 Correct 586 ms 65912 KB Output is correct
40 Correct 1079 ms 83040 KB Output is correct
41 Correct 678 ms 65808 KB Output is correct
42 Correct 689 ms 65896 KB Output is correct
43 Correct 225 ms 24780 KB Output is correct
44 Correct 2754 ms 199256 KB Output is correct
45 Correct 2973 ms 209576 KB Output is correct
46 Correct 2983 ms 216216 KB Output is correct
47 Correct 3281 ms 219112 KB Output is correct
48 Correct 3035 ms 197696 KB Output is correct
49 Correct 1354 ms 112276 KB Output is correct
50 Correct 714 ms 64612 KB Output is correct
51 Correct 2604 ms 178224 KB Output is correct
52 Correct 964 ms 89544 KB Output is correct
53 Correct 21 ms 6564 KB Output is correct
54 Correct 3047 ms 208888 KB Output is correct
55 Correct 2762 ms 215140 KB Output is correct
56 Correct 3254 ms 219056 KB Output is correct
57 Correct 2092 ms 166824 KB Output is correct
58 Correct 2244 ms 169940 KB Output is correct
59 Correct 2735 ms 214364 KB Output is correct
60 Correct 2198 ms 167064 KB Output is correct
61 Correct 2252 ms 169500 KB Output is correct
62 Correct 1321 ms 109308 KB Output is correct
63 Correct 57 ms 13152 KB Output is correct
64 Correct 1861 ms 161772 KB Output is correct
65 Correct 1737 ms 145692 KB Output is correct
66 Correct 995 ms 88404 KB Output is correct
67 Correct 1314 ms 127804 KB Output is correct
68 Correct 639 ms 62216 KB Output is correct
69 Correct 3256 ms 218580 KB Output is correct
70 Correct 2431 ms 211524 KB Output is correct
71 Correct 2979 ms 197548 KB Output is correct
72 Correct 1306 ms 111656 KB Output is correct
73 Correct 2658 ms 178096 KB Output is correct
74 Correct 858 ms 77996 KB Output is correct
75 Correct 831 ms 77532 KB Output is correct
76 Correct 1006 ms 86416 KB Output is correct
77 Correct 1174 ms 101076 KB Output is correct
78 Correct 860 ms 79296 KB Output is correct
79 Correct 663 ms 64952 KB Output is correct
80 Correct 646 ms 65892 KB Output is correct
81 Correct 1167 ms 83116 KB Output is correct
82 Correct 699 ms 65944 KB Output is correct
83 Correct 782 ms 65852 KB Output is correct
84 Correct 186 ms 20648 KB Output is correct
85 Correct 3122 ms 212448 KB Output is correct
86 Execution timed out 4082 ms 241864 KB Time limit exceeded
87 Halted 0 ms 0 KB -