fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define NeOWami signed
  5. #define ft first
  6. #define sc second
  7. #define int long long
  8. using pii = pair<int, int>;
  9. template<class T> using heapmin = priority_queue<T, vector<T>, greater<T>>;
  10. const int N = 1e6 + 5;
  11. const int inf = 1e18;
  12. int n, id[N], dist[N], par[N];
  13. pii a[N], b[N];
  14. vector<pii> G[N];
  15. bool ckmin(int &u, int v) {
  16.     if (u > v) return u = v, 1;
  17.     return 0;
  18. }
  19. bool cmp(int i, int j) {
  20.     return b[i].ft + b[i].sc < b[j].ft + b[j].sc;
  21. }
  22. void SweepLine() {
  23.     for (int i = 1; i <= n; i++) id[i] = i;
  24.     sort(id + 1, id + n + 1, cmp);
  25.     map<int, int, greater<int>> active;
  26.     for (int i = 1; i <= n; i++) {
  27.         int u = id[i];
  28.         for (map<int, int>::iterator it = active.lower_bound(b[u].ft); it != active.end(); active.erase(it++)) {
  29.             int v = it->sc;
  30.             if (b[u].ft - b[u].sc > b[v].ft - b[v].sc) break;
  31.             G[u].push_back({b[u].ft - b[v].ft + b[u].sc - b[v].sc, v});
  32.             G[v].push_back({b[u].ft - b[v].ft + b[u].sc - b[v].sc, u});
  33.         }
  34.         active[b[u].ft] = u;
  35.     }
  36. }
  37. NeOWami main() {
  38.     cin.tie(NULL)->sync_with_stdio(false);
  39.     if(ifstream("DESERT.inp")) {
  40.         freopen("DESERT.inp", "r", stdin);
  41.         freopen("DESERT.out", "w", stdout);
  42.     }
  43.     cin >> n;
  44.     for (int i = 1; i <= n; i++) cin >> a[i].ft >> a[i].sc;
  45.     for (int i = 1; i <= n; i++) b[i] = a[i];
  46.     for (int rot = 0; rot < 4; rot++) {
  47.         SweepLine();
  48.         for (int i = 1; i <= n; i++) {
  49.             if (rot & 1) b[i].ft *= -1;
  50.             else swap(b[i].ft, b[i].sc);
  51.         }
  52.     }
  53.     fill(dist + 1, dist + n + 1, inf);
  54.     dist[1] = 0;
  55.     heapmin<pii> Q;
  56.     Q.push({0, 1});
  57.     while(!Q.empty()) {
  58.         int old = Q.top().ft, u = Q.top().sc;
  59.         Q.pop();
  60.         for (pii item: G[u]) {
  61.             int w = max(item.ft, old), v = item.sc;
  62.             if (ckmin(dist[v], w)) {
  63.                 Q.push({w, v});
  64.                 par[v] = u;
  65.             }
  66.         }
  67.     }
  68.     vector<int> ans;
  69.     for (int i = n; i; i = par[i]) ans.push_back(i);
  70.     reverse(ans.begin(), ans.end());
  71.     cout << dist[n] << "\n";
  72.     for (int item: ans) cout << item << " ";
  73. }
Success #stdin #stdout 0.01s 31076KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/atE6TY
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!