Submission #373023

#	Time	Username	Problem	Language	Result	Execution time	Memory
373023		Kanon	Sky Walking (IOI19_walk)	C++14	10 / 100	4103 ms	497392 KiB

walk

#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);

struct edge {
  int f;
  int t;
  int dis;
};

vector<long long> calc(int n, int s, int t, vector<vector<edge>> g) {
  vector<long long> ret(n, LLONG_MAX);
  ret[s] = 0;
  set<pair<long long, int>> que;
  vector<int> was(n);
  que.insert({ret[s], s});
  while(que.size()) {
    int v = que.begin()->second;
    que.erase(que.begin());
    if(was[v]) continue;
    was[v] = 1;
    for(edge e : g[v]) {
      int u = e.t;
      if(ret[u] > ret[v] + e.dis) {
        ret[u] = ret[v] + e.dis;
        que.insert(make_pair(ret[u], u));
      }
    }
  }
  return ret;
}

long long min_distance(vector<int> px, vector<int> h, vector<int> l, vector<int> r, vector<int> py, int s, int t) {
  int n = px.size();
  int m = py.size();
  set<pair<int, int>> p;
  auto add = [&](int x, int y) {
    p.insert({x, y});
  };
  add(px[s], 0);
  add(px[t], 0);
  for(int i = 0; i < m; i++) {
    add(px[l[i]], py[i]);
    add(px[r[i]], py[i]);
  }
  // nearest pole
  {
    vector<int> order(m);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j){return py[i] > py[j];});
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int i, int j){return h[i] > h[j];});
    int cur = 0;
    set<int> xs;
    for(int i : order) {
      while(cur < n && h[id[cur]] >= py[i]) {
        xs.insert(px[id[cur]]);
        cur++;
      }
      int L = px[l[i]], R = px[r[i]];
      if(L < px[s] && px[s] < R) {
        if(xs.find(px[s]) != xs.end()) add(px[s], py[i]);
        else {
          int u = *prev(xs.lower_bound(px[s]));
          int v = *xs.upper_bound(px[s]);
          add(u, py[i]); add(v, py[i]);
        }
      }
      if(L < px[t] && px[t] < R) {
        if(xs.find(px[t]) != xs.end()) add(px[t], py[i]);
        else {
          int u = *prev(xs.lower_bound(px[t]));
          int v = *xs.upper_bound(px[t]);
          add(u, py[i]); add(v, py[i]);
        }
      }
    }
  }
  // nearest hor
  {
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int i, int j){return h[i] > h[j];});
    int cur = 0;
    set<int> xs;
    vector<pair<int, int>> pos;
    for(auto i : p) pos.push_back(i);
    sort(pos.begin(), pos.end(), [&](pair<int, int> i, pair<int, int> j){return i.second > j.second;});
    for(auto it = pos.begin(); it != pos.end(); it++) {
      int y = it->second;
      while(cur < n && h[id[cur]] >= y) {
        xs.insert(px[id[cur]]);
        cur++;
      }
      auto i = xs.find(it->first);
      assert(i != xs.end());
      if(i != xs.begin()) add(*prev(i), y);
      if(i != prev(xs.end())) add(*next(i), y);
    }
  }
  // nearest ver
  {
    vector<vector<int>> rev(n);
    for(int i = 0; i < m; i++) {
      rev[l[i]].push_back(i);
      if(r[i] < n - 1) rev[r[i] + 1].push_back(~i);
    }
    int cur = 0;
    set<int> ys;
    for(auto v : p) {
      while(cur < n && px[cur] <= v.first) {
        for(int i : rev[cur]) {
          if(i < 0) {
            ys.erase(py[~i]);
          } else {
            ys.insert(py[i]);
          }
        }
        cur++;
      }
      auto it = ys.find(v.second);
      if(it == ys.end()) continue;
      if(it != ys.begin()) add(v.first, *prev(it));
      if(it != prev(ys.end()) && *next(it) <= h[cur - 1]) add(v.first, *next(it));
    }
  }
  //numerate
  int sz = p.size();
  map<pair<int, int>, int> id;
  for(auto i : p) {
    int fp = id.size();
    id[i] = fp;
  }
  vector<vector<edge>> g(sz);
  // add ver edged
  int cnt = 0;
  for(auto it = p.begin(); next(it) != p.end(); it++) {
    if(it->first == next(it)->first) {
      int u = cnt;
      int v = cnt + 1;
      int dis = abs(it->second - next(it)->second);
      g[u].push_back({u, v, dis});
      g[v].push_back({v, u, dis});
    }
    cnt++;
  }
  // add hor edge
  map<int, vector<int>> Y;
  for(auto i : p) Y[i.second].push_back(i.first);
  for(int i = 0; i < m; i++) {
    int y = py[i];
    int L = px[l[i]];
    int R = px[r[i]];
    for(int j = lower_bound(Y[y].begin(), Y[y].end(), L) - Y[y].begin(); Y[y][j] < R; j++) {
      int u = id[make_pair(Y[y][j], y)];
      int v = id[make_pair(Y[y][j + 1], y)];
      int dis = abs(Y[y][j] - Y[y][j + 1]);
      g[u].push_back({u, v, dis});
      g[v].push_back({v, u, dis});
    }
  }
  //
  int ss = id[make_pair(px[s], 0)];
  int tt = id[make_pair(px[t], 0)];
  vector<long long> ret = calc(sz, ss, tt, g);
  if(ret[tt] == LLONG_MAX) return -1;
  return ret[tt];
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43