oj.uz

Submission #147981

# Submission time Handle Problem Language Result Execution time Memory
147981 2019-08-31T10:28:54 Z Xylofo Sky Walking (IOI19_walk) C++14
57 / 100
 4000 ms 245920 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

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:70:16: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
       for(auto [hh, _] : perBuild[i]) {
                ^
walk.cpp:70: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:101: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 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 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 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 348 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 256 KB Output is correct
3 Correct 1650 ms 128612 KB Output is correct
4 Correct 1543 ms 133884 KB Output is correct
5 Correct 1264 ms 105028 KB Output is correct
6 Correct 1190 ms 97740 KB Output is correct
7 Correct 1091 ms 105072 KB Output is correct
8 Correct 1916 ms 143812 KB Output is correct
9 Correct 1309 ms 123544 KB Output is correct
10 Correct 1865 ms 144352 KB Output is correct
11 Correct 1237 ms 98612 KB Output is correct
12 Correct 681 ms 64644 KB Output is correct
13 Correct 1662 ms 149160 KB Output is correct
14 Correct 917 ms 70380 KB Output is correct
15 Correct 857 ms 71284 KB Output is correct
16 Correct 732 ms 69236 KB Output is correct
17 Correct 708 ms 66388 KB Output is correct
18 Correct 1125 ms 75640 KB Output is correct
19 Correct 19 ms 3764 KB Output is correct
20 Correct 260 ms 35120 KB Output is correct
21 Correct 615 ms 64888 KB Output is correct
22 Correct 645 ms 65216 KB Output is correct
23 Correct 1177 ms 83208 KB Output is correct
24 Correct 656 ms 65992 KB Output is correct
25 Correct 671 ms 65932 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 24948 KB Output is correct
2 Correct 2509 ms 175088 KB Output is correct
3 Correct 2503 ms 182096 KB Output is correct
4 Correct 2581 ms 188300 KB Output is correct
5 Correct 2783 ms 191132 KB Output is correct
6 Correct 2560 ms 176588 KB Output is correct
7 Correct 1187 ms 98616 KB Output is correct
8 Correct 670 ms 64588 KB Output is correct
9 Correct 2247 ms 163988 KB Output is correct
10 Correct 1048 ms 89456 KB Output is correct
11 Correct 21 ms 6308 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 24948 KB Output is correct
2 Correct 2509 ms 175088 KB Output is correct
3 Correct 2503 ms 182096 KB Output is correct
4 Correct 2581 ms 188300 KB Output is correct
5 Correct 2783 ms 191132 KB Output is correct
6 Correct 2560 ms 176588 KB Output is correct
7 Correct 1187 ms 98616 KB Output is correct
8 Correct 670 ms 64588 KB Output is correct
9 Correct 2247 ms 163988 KB Output is correct
10 Correct 1048 ms 89456 KB Output is correct
11 Correct 21 ms 6308 KB Output is correct
12 Correct 2487 ms 181584 KB Output is correct
13 Correct 2452 ms 187444 KB Output is correct
14 Correct 2891 ms 191156 KB Output is correct
15 Correct 1823 ms 147888 KB Output is correct
16 Correct 1871 ms 151096 KB Output is correct
17 Correct 2420 ms 187000 KB Output is correct
18 Correct 1943 ms 147972 KB Output is correct
19 Correct 2000 ms 150716 KB Output is correct
20 Correct 1180 ms 95992 KB Output is correct
21 Correct 63 ms 13152 KB Output is correct
22 Correct 1615 ms 144200 KB Output is correct
23 Correct 1419 ms 128848 KB Output is correct
24 Correct 941 ms 85156 KB Output is correct
25 Correct 1214 ms 118484 KB Output is correct
26 Correct 623 ms 61428 KB Output is correct
27 Correct 2818 ms 190948 KB Output is correct
28 Correct 2115 ms 184832 KB Output is correct
29 Correct 2576 ms 176528 KB Output is correct
30 Correct 1259 ms 98056 KB Output is correct
31 Correct 2347 ms 163852 KB Output is correct
32 Correct 838 ms 77928 KB Output is correct
33 Correct 777 ms 77628 KB Output is correct
34 Correct 991 ms 86404 KB Output is correct
35 Correct 1117 ms 95636 KB Output is correct
36 Correct 849 ms 78416 KB Output is correct
37 Correct 655 ms 64888 KB Output is correct
38 Correct 605 ms 65100 KB Output is correct
39 Correct 1070 ms 83060 KB Output is correct
40 Correct 671 ms 66056 KB Output is correct
41 Correct 691 ms 65848 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 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 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 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 348 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 256 KB Output is correct
20 Correct 1650 ms 128612 KB Output is correct
21 Correct 1543 ms 133884 KB Output is correct
22 Correct 1264 ms 105028 KB Output is correct
23 Correct 1190 ms 97740 KB Output is correct
24 Correct 1091 ms 105072 KB Output is correct
25 Correct 1916 ms 143812 KB Output is correct
26 Correct 1309 ms 123544 KB Output is correct
27 Correct 1865 ms 144352 KB Output is correct
28 Correct 1237 ms 98612 KB Output is correct
29 Correct 681 ms 64644 KB Output is correct
30 Correct 1662 ms 149160 KB Output is correct
31 Correct 917 ms 70380 KB Output is correct
32 Correct 857 ms 71284 KB Output is correct
33 Correct 732 ms 69236 KB Output is correct
34 Correct 708 ms 66388 KB Output is correct
35 Correct 1125 ms 75640 KB Output is correct
36 Correct 19 ms 3764 KB Output is correct
37 Correct 260 ms 35120 KB Output is correct
38 Correct 615 ms 64888 KB Output is correct
39 Correct 645 ms 65216 KB Output is correct
40 Correct 1177 ms 83208 KB Output is correct
41 Correct 656 ms 65992 KB Output is correct
42 Correct 671 ms 65932 KB Output is correct
43 Correct 237 ms 24948 KB Output is correct
44 Correct 2509 ms 175088 KB Output is correct
45 Correct 2503 ms 182096 KB Output is correct
46 Correct 2581 ms 188300 KB Output is correct
47 Correct 2783 ms 191132 KB Output is correct
48 Correct 2560 ms 176588 KB Output is correct
49 Correct 1187 ms 98616 KB Output is correct
50 Correct 670 ms 64588 KB Output is correct
51 Correct 2247 ms 163988 KB Output is correct
52 Correct 1048 ms 89456 KB Output is correct
53 Correct 21 ms 6308 KB Output is correct
54 Correct 2487 ms 181584 KB Output is correct
55 Correct 2452 ms 187444 KB Output is correct
56 Correct 2891 ms 191156 KB Output is correct
57 Correct 1823 ms 147888 KB Output is correct
58 Correct 1871 ms 151096 KB Output is correct
59 Correct 2420 ms 187000 KB Output is correct
60 Correct 1943 ms 147972 KB Output is correct
61 Correct 2000 ms 150716 KB Output is correct
62 Correct 1180 ms 95992 KB Output is correct
63 Correct 63 ms 13152 KB Output is correct
64 Correct 1615 ms 144200 KB Output is correct
65 Correct 1419 ms 128848 KB Output is correct
66 Correct 941 ms 85156 KB Output is correct
67 Correct 1214 ms 118484 KB Output is correct
68 Correct 623 ms 61428 KB Output is correct
69 Correct 2818 ms 190948 KB Output is correct
70 Correct 2115 ms 184832 KB Output is correct
71 Correct 2576 ms 176528 KB Output is correct
72 Correct 1259 ms 98056 KB Output is correct
73 Correct 2347 ms 163852 KB Output is correct
74 Correct 838 ms 77928 KB Output is correct
75 Correct 777 ms 77628 KB Output is correct
76 Correct 991 ms 86404 KB Output is correct
77 Correct 1117 ms 95636 KB Output is correct
78 Correct 849 ms 78416 KB Output is correct
79 Correct 655 ms 64888 KB Output is correct
80 Correct 605 ms 65100 KB Output is correct
81 Correct 1070 ms 83060 KB Output is correct
82 Correct 671 ms 66056 KB Output is correct
83 Correct 691 ms 65848 KB Output is correct
84 Correct 180 ms 20476 KB Output is correct
85 Correct 2970 ms 185472 KB Output is correct
86 Correct 3521 ms 214232 KB Output is correct
87 Correct 128 ms 20972 KB Output is correct
88 Correct 136 ms 20988 KB Output is correct
89 Correct 124 ms 20964 KB Output is correct
90 Correct 54 ms 9304 KB Output is correct
91 Correct 3 ms 632 KB Output is correct
92 Correct 45 ms 7104 KB Output is correct
93 Correct 814 ms 67252 KB Output is correct
94 Correct 61 ms 13360 KB Output is correct
95 Correct 1751 ms 151860 KB Output is correct
96 Correct 1424 ms 130220 KB Output is correct
97 Correct 1089 ms 89160 KB Output is correct
98 Correct 1231 ms 118400 KB Output is correct
99 Execution timed out 4026 ms 245920 KB Time limit exceeded
100 Halted 0 ms 0 KB -