Submission #373034

#	Time	Username	Problem	Language	Result	Execution time	Memory
373034		Kanon	Sky Walking (IOI19_walk)	C++14	0 / 100	3790 ms	309428 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(make_pair(x, y));
  };
  add(px[s], 0);
  add(px[t], 0);

  {
    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);
    }

    set<int> ys;
    for(int cur = 0; cur < n; cur++) {
      for(int i : rev[cur]) {
        if(i < 0) {
          ys.erase(py[~i]);
        } else {
          ys.insert(py[i]);
        }
      }

      for(int j : ys) {
        if(j > h[cur]) break;
        add(px[cur], j);
      }

    }
  }
  //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
  for(auto it = p.begin(); next(it) != p.end(); it++) {
    if(it->first == next(it)->first) {
      int u = id[*it];
      int v = id[*next(it)];
      int dis = abs(it->second - next(it)->second);
      g[u].push_back({u, v, dis});
      g[v].push_back({v, u, dis});
    }
  }
  // add hor edge
  map<int, vector<int>> Y;
  long long bug = 0;
  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]];
    bug -= R - L;
    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]);
      bug += dis;
      g[u].push_back({u, v, dis});
      g[v].push_back({v, u, dis});
    }
  }
  assert(bug == 0);
  //
  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];
}

/*int main() {
  cout << min_distance({0, 3, 5, 7, 10, 12, 14},
{8, 7, 9, 7, 6, 6, 9},
{0, 0, 0, 2, 2, 3, 4},
{1, 2, 6, 3, 6, 4, 6},
{1, 6, 8, 1, 7, 2, 5},
1, 5);
  return 0;
}*/

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