Submission #281642

#	Time	Username	Problem	Language	Result	Execution time	Memory
281642		Vimmer	Sky Walking (IOI19_walk)	C++14	10 / 100	3350 ms	1048580 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100005

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair <int, int> pt;

vector <vector <pair <int, int> > > g;

vector <int> nums[N], who[N], db[N], del[N];

vector <ll> dst;

gp_hash_table <int, int> dob;

gp_hash_table <int, gp_hash_table <int, int> > idr;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int to)
{
    if (s == to) return 0;

    int n = sz(x);

    int m = sz(l);

    set <pair <int, int> > st; st.clear();

    for (int j = 0; j < m; j++)
        {db[l[j]].pb(j); del[r[j]].pb(j);}

    for (int i = 0; i < n; i++)
    {
        for (auto j : db[i])
            st.insert({y[j], j});

        auto it = st.upper_bound(pt(h[i], 1e9));

        if (it != st.begin())
        {
            it--;

            while (1)
            {
                who[(*it).S].pb(i);

                nums[i].pb((*it).S);

                if (it == st.begin()) break;

                it--;
            }
        }
        for (auto j : del[i])
            st.erase({y[j], j});
    }

    int id = 0;

    ll ans = 1e18;

    set <pair <ll, int> > str;

    set <int> se; se.clear();

    for (int i = 0; i < n; i++)
      for (auto j : nums[i])
      {
          if (i == to) {se.insert(id); dob[id] = y[j];}

          idr[i][j] = id++;

          g.emplace_back();

          dst.emplace_back();

          for (auto jr : nums[i])
          {
              if (jr == j) break;

              g[id - 1].pb({idr[i][jr], abs(y[jr] - y[j])});

              g[idr[i][jr]].pb({id - 1, abs(y[jr] - y[j])});
          }

          if (s == i) {dst[id - 1] = 0; str.insert({y[j], id - 1});}
      }

    fill(dst.begin(), dst.end(), -1);

    for (int i = 0; i < n; i++)
        for (auto j : nums[i])
          for (auto I : who[j])
          {
              if (I == i) continue;

              g[idr[i][j]].pb({idr[I][j], abs(x[i] - x[I])});
          }

    while (sz(str))
    {
        pair <ll, int> pt = *str.begin(); str.erase(str.begin());

        if (se.find(pt.S) != se.end()) {ans = min(ans, pt.F + dob[pt.S]); se.erase(pt.S); if (sz(se) == 0) return ans;}

        for (auto itr : g[pt.S])
        {
            ll s = pt.F + itr.S;

            if (dst[itr.F] != -1 && dst[itr.F] <= s) continue;

            dst[itr.F] = s;

            str.insert({s, itr.F});
        }
    }

    if (ans == 1e18) return -1;

	return ans;
}

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