oj.uz

Submission #147973

# Submission time Handle Problem Language Result Execution time Memory
147973 2019-08-31T10:23:03 Z Xylofo Sky Walking (IOI19_walk) C++14
57 / 100
 4000 ms 250000 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: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 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 452 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 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 372 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 1631 ms 128884 KB Output is correct
4 Correct 1528 ms 133864 KB Output is correct
5 Correct 1062 ms 105032 KB Output is correct
6 Correct 1109 ms 97656 KB Output is correct
7 Correct 1126 ms 104956 KB Output is correct
8 Correct 1869 ms 143940 KB Output is correct
9 Correct 1371 ms 123528 KB Output is correct
10 Correct 1708 ms 144380 KB Output is correct
11 Correct 1200 ms 101544 KB Output is correct
12 Correct 703 ms 68628 KB Output is correct
13 Correct 1721 ms 153068 KB Output is correct
14 Correct 949 ms 74808 KB Output is correct
15 Correct 1002 ms 74296 KB Output is correct
16 Correct 746 ms 71900 KB Output is correct
17 Correct 690 ms 69096 KB Output is correct
18 Correct 1025 ms 78408 KB Output is correct
19 Correct 20 ms 4032 KB Output is correct
20 Correct 267 ms 37508 KB Output is correct
21 Correct 630 ms 67584 KB Output is correct
22 Correct 593 ms 69108 KB Output is correct
23 Correct 1076 ms 85944 KB Output is correct
24 Correct 686 ms 68864 KB Output is correct
25 Correct 877 ms 68488 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 24788 KB Output is correct
2 Correct 2420 ms 175004 KB Output is correct
3 Correct 2547 ms 182100 KB Output is correct
4 Correct 2686 ms 188400 KB Output is correct
5 Correct 3010 ms 191296 KB Output is correct
6 Correct 2971 ms 176808 KB Output is correct
7 Correct 1164 ms 98412 KB Output is correct
8 Correct 785 ms 64528 KB Output is correct
9 Correct 2378 ms 163868 KB Output is correct
10 Correct 1073 ms 89668 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 24788 KB Output is correct
2 Correct 2420 ms 175004 KB Output is correct
3 Correct 2547 ms 182100 KB Output is correct
4 Correct 2686 ms 188400 KB Output is correct
5 Correct 3010 ms 191296 KB Output is correct
6 Correct 2971 ms 176808 KB Output is correct
7 Correct 1164 ms 98412 KB Output is correct
8 Correct 785 ms 64528 KB Output is correct
9 Correct 2378 ms 163868 KB Output is correct
10 Correct 1073 ms 89668 KB Output is correct
11 Correct 21 ms 6564 KB Output is correct
12 Correct 2629 ms 181580 KB Output is correct
13 Correct 2357 ms 187264 KB Output is correct
14 Correct 3105 ms 191052 KB Output is correct
15 Correct 1877 ms 148024 KB Output is correct
16 Correct 1978 ms 150892 KB Output is correct
17 Correct 2342 ms 187004 KB Output is correct
18 Correct 1961 ms 147968 KB Output is correct
19 Correct 1941 ms 150780 KB Output is correct
20 Correct 1217 ms 96240 KB Output is correct
21 Correct 55 ms 13148 KB Output is correct
22 Correct 1639 ms 143964 KB Output is correct
23 Correct 1350 ms 128824 KB Output is correct
24 Correct 918 ms 85216 KB Output is correct
25 Correct 1292 ms 118456 KB Output is correct
26 Correct 669 ms 62248 KB Output is correct
27 Correct 2934 ms 190920 KB Output is correct
28 Correct 2129 ms 184716 KB Output is correct
29 Correct 2906 ms 176540 KB Output is correct
30 Correct 1126 ms 98096 KB Output is correct
31 Correct 2550 ms 163868 KB Output is correct
32 Correct 870 ms 78128 KB Output is correct
33 Correct 824 ms 77480 KB Output is correct
34 Correct 1006 ms 86452 KB Output is correct
35 Correct 1081 ms 95508 KB Output is correct
36 Correct 828 ms 78308 KB Output is correct
37 Correct 627 ms 64832 KB Output is correct
38 Correct 592 ms 65900 KB Output is correct
39 Correct 1097 ms 83140 KB Output is correct
40 Correct 675 ms 65900 KB Output is correct
41 Correct 673 ms 65960 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 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 452 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 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 372 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 1631 ms 128884 KB Output is correct
21 Correct 1528 ms 133864 KB Output is correct
22 Correct 1062 ms 105032 KB Output is correct
23 Correct 1109 ms 97656 KB Output is correct
24 Correct 1126 ms 104956 KB Output is correct
25 Correct 1869 ms 143940 KB Output is correct
26 Correct 1371 ms 123528 KB Output is correct
27 Correct 1708 ms 144380 KB Output is correct
28 Correct 1200 ms 101544 KB Output is correct
29 Correct 703 ms 68628 KB Output is correct
30 Correct 1721 ms 153068 KB Output is correct
31 Correct 949 ms 74808 KB Output is correct
32 Correct 1002 ms 74296 KB Output is correct
33 Correct 746 ms 71900 KB Output is correct
34 Correct 690 ms 69096 KB Output is correct
35 Correct 1025 ms 78408 KB Output is correct
36 Correct 20 ms 4032 KB Output is correct
37 Correct 267 ms 37508 KB Output is correct
38 Correct 630 ms 67584 KB Output is correct
39 Correct 593 ms 69108 KB Output is correct
40 Correct 1076 ms 85944 KB Output is correct
41 Correct 686 ms 68864 KB Output is correct
42 Correct 877 ms 68488 KB Output is correct
43 Correct 225 ms 24788 KB Output is correct
44 Correct 2420 ms 175004 KB Output is correct
45 Correct 2547 ms 182100 KB Output is correct
46 Correct 2686 ms 188400 KB Output is correct
47 Correct 3010 ms 191296 KB Output is correct
48 Correct 2971 ms 176808 KB Output is correct
49 Correct 1164 ms 98412 KB Output is correct
50 Correct 785 ms 64528 KB Output is correct
51 Correct 2378 ms 163868 KB Output is correct
52 Correct 1073 ms 89668 KB Output is correct
53 Correct 21 ms 6564 KB Output is correct
54 Correct 2629 ms 181580 KB Output is correct
55 Correct 2357 ms 187264 KB Output is correct
56 Correct 3105 ms 191052 KB Output is correct
57 Correct 1877 ms 148024 KB Output is correct
58 Correct 1978 ms 150892 KB Output is correct
59 Correct 2342 ms 187004 KB Output is correct
60 Correct 1961 ms 147968 KB Output is correct
61 Correct 1941 ms 150780 KB Output is correct
62 Correct 1217 ms 96240 KB Output is correct
63 Correct 55 ms 13148 KB Output is correct
64 Correct 1639 ms 143964 KB Output is correct
65 Correct 1350 ms 128824 KB Output is correct
66 Correct 918 ms 85216 KB Output is correct
67 Correct 1292 ms 118456 KB Output is correct
68 Correct 669 ms 62248 KB Output is correct
69 Correct 2934 ms 190920 KB Output is correct
70 Correct 2129 ms 184716 KB Output is correct
71 Correct 2906 ms 176540 KB Output is correct
72 Correct 1126 ms 98096 KB Output is correct
73 Correct 2550 ms 163868 KB Output is correct
74 Correct 870 ms 78128 KB Output is correct
75 Correct 824 ms 77480 KB Output is correct
76 Correct 1006 ms 86452 KB Output is correct
77 Correct 1081 ms 95508 KB Output is correct
78 Correct 828 ms 78308 KB Output is correct
79 Correct 627 ms 64832 KB Output is correct
80 Correct 592 ms 65900 KB Output is correct
81 Correct 1097 ms 83140 KB Output is correct
82 Correct 675 ms 65900 KB Output is correct
83 Correct 673 ms 65960 KB Output is correct
84 Correct 169 ms 21060 KB Output is correct
85 Correct 2742 ms 187564 KB Output is correct
86 Correct 3332 ms 218304 KB Output is correct
87 Correct 121 ms 23276 KB Output is correct
88 Correct 134 ms 23284 KB Output is correct
89 Correct 121 ms 23272 KB Output is correct
90 Correct 57 ms 9304 KB Output is correct
91 Correct 4 ms 676 KB Output is correct
92 Correct 43 ms 7384 KB Output is correct
93 Correct 798 ms 69812 KB Output is correct
94 Correct 59 ms 15452 KB Output is correct
95 Correct 1813 ms 155764 KB Output is correct
96 Correct 1449 ms 134048 KB Output is correct
97 Correct 1063 ms 93088 KB Output is correct
98 Correct 1264 ms 122124 KB Output is correct
99 Execution timed out 4064 ms 250000 KB Time limit exceeded
100 Halted 0 ms 0 KB -