Submission #422710

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
422710	2021-06-10T10:59:37 Z	SSRS	Sky Walking (IOI19_walk)	C++14	Compilation error	0 ms	0 KB

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];
}
int main(){
  vector<int> x1 = {0, 3, 5, 7, 10, 12, 14};
  vector<int> h1 = {8, 7, 9, 7, 6, 6, 9};
  vector<int> l1 = {0, 0, 0, 2, 2, 3, 4};
  vector<int> r1 = {1, 2, 6, 3, 6, 4, 6};
  vector<int> y1 = {1, 6, 8, 1, 7, 2, 5};
  int s1 = 1;
  int g1 = 5;
  cout << min_distance(x1, h1, l1, r1, y1, s1, g1) << endl;
  vector<int> x2 = {0, 4, 5, 6, 9};
  vector<int> h2 = {6, 6, 6, 6, 6};
  vector<int> l2 = {3, 1, 0};
  vector<int> r2 = {4, 3, 2};
  vector<int> y2 = {1, 3, 6};
  int s2 = 0;
  int g2 = 4;
  cout << min_distance(x2, h2, l2, r2, y2, s2, g2) << endl;
}

Compilation message

/usr/bin/ld: /tmp/ccl6Dw7N.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccce3zcR.o:walk.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status