Submission #422712

#	Time	Username	Problem	Language	Result	Execution time	Memory
422712		SSRS	Sky Walking (IOI19_walk)	C++14	24 / 100	4112 ms	482996 KiB

walk

#include <bits/stdc++.h>
using namespace std;
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
  int n = x.size();
  int m = y.size();
  vector<tuple<int, int, int>> T;
  for (int i = 0; i < n; i++){
    T.push_back(make_tuple(h[i], 1, i));
  }
  for (int i = 0; i < m; i++){
    T.push_back(make_tuple(y[i], 0, i));
  }
  sort(T.begin(), T.end(), greater<tuple<int, int, int>>());
  vector<vector<int>> id(m);
  set<int> st;
  for (int i = 0; i < n + m; i++){
    int t = get<1>(T[i]);
    int p = get<2>(T[i]);
    if (t == 0){
      auto itr = st.lower_bound(l[p]);
      while (true){
        id[p].push_back(*itr);
        if (*itr == r[p]){
          break;
        }
        itr++;
      }
    }
    if (t == 1){
      st.insert(p);
    }
  }
  vector<vector<int>> h2(n);
  for (int i = 0; i < n; i++){
    h2[i].push_back(0);
  }
  for (int i = 0; i < m; i++){
    for (int j : id[i]){
      h2[j].push_back(y[i]);
    }
  }
  for (int i = 0; i < n; i++){
    sort(h2[i].begin(), h2[i].end());
    h2[i].erase(unique(h2[i].begin(), h2[i].end()), h2[i].end());
  }
  int V = 0;
  vector<vector<int>> id2(n);
  for (int i = 0; i < n; i++){
    int cnt = h2[i].size();
    id2[i] = vector<int>(cnt);
    for (int j = 0; j < cnt; j++){
      id2[i][j] = V;
      V++;
    }
  }
  vector<vector<pair<int, int>>> E(V);
  for (int i = 0; i < n; i++){
    int cnt = h2[i].size();
    for (int j = 0; j < cnt - 1; j++){
      int v = id2[i][j];
      int w = id2[i][j + 1];
      int d = h2[i][j + 1] - h2[i][j];
      E[v].push_back(make_pair(d, w));
      E[w].push_back(make_pair(d, v));
    }
  }
  for (int i = 0; i < m; i++){
    int cnt = id[i].size();
    vector<int> t(cnt);
    for (int j = 0; j < cnt; j++){
      int p = lower_bound(h2[id[i][j]].begin(), h2[id[i][j]].end(), y[i]) - h2[id[i][j]].begin();
      t[j] = id2[id[i][j]][p];
    }
    for (int j = 0; j < cnt - 1; j++){
      int v = t[j];
      int w = t[j + 1];
      int d = x[id[i][j + 1]] - x[id[i][j]];
      E[v].push_back(make_pair(d, w));
      E[w].push_back(make_pair(d, v));
    }
  }
  int s2 = id2[s][0];
  int g2 = id2[g][0];
  vector<long long> d(V, -1);
  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  pq.push(make_pair(0, s2));
  while (!pq.empty()){
    long long dd = pq.top().first;
    int v = pq.top().second;
    pq.pop();
    if (d[v] == -1){
      d[v] = dd;
      for (auto P : E[v]){
        int w = P.second;
        if (d[w] == -1){
          pq.push(make_pair(dd + P.first, w));
        }
      }
    }
  }
  return d[g2];
}

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