oj.uz

Submission #281686

# Submission time Handle Problem Language Result Execution time Memory
281686 2020-08-23T09:57:07 Z Vimmer Sky Walking (IOI19_walk) C++14
10 / 100
 2165 ms 1048584 KB 
#include "walk.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")

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

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair <int, int> ptr;
typedef array <int, 3> a3;

vector <vector <int> > g;

vector <a3> edge;

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

vector <ll> dst;

gp_hash_table <int, int> idr[N];

void add(int a, int b, int cost)
{
    g[a].pb(sz(edge));

    g[b].pb(sz(edge));

    edge.pb({a, b, cost});
}

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int to)
{
    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(ptr(h[i], 1e9));

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

            while (1)
            {
                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 <pair <int, int> > se; se.clear();

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

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

          g.emplace_back();

          dst.pb(-1);

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

              add(id - 1, idr[i][jr], abs(y[jr] - y[j]));
          }

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

    for (int i = 0; i < n; i++)
        for (auto j : nums[i])
        {
            for (auto I : who[j])
              add(idr[i][j], idr[I][j], abs(x[i] - x[I]));

            who[j].pb(i);
        }

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

        if (pt.F >= ans) return ans;

        auto it = se.upper_bound(ptr(pt.S, 1e9 + 1e9));

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

            if ((*it).F == pt.S) {ans = min(ans, pt.F + (*it).S); se.erase(it); if (sz(se) == 0) return ans;}
        }

        for (auto ip : g[pt.S])
        {
            a3 itr = edge[ip];

            ll s = pt.F + itr[2];

            if (itr[0] == pt.S) swap(itr[0], itr[1]);

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

            if (ans <= s) continue;

            str.erase({dst[itr[0]], itr[0]});

            dst[itr[0]] = s;

            str.insert({s, itr[0]});
        }
    }

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

	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 30848 KB Output is correct
2 Correct 31 ms 30848 KB Output is correct
3 Correct 31 ms 30976 KB Output is correct
4 Correct 31 ms 30840 KB Output is correct
5 Correct 32 ms 31224 KB Output is correct
6 Correct 32 ms 31232 KB Output is correct
7 Correct 34 ms 31232 KB Output is correct
8 Correct 32 ms 31096 KB Output is correct
9 Correct 31 ms 30848 KB Output is correct
10 Correct 33 ms 31480 KB Output is correct
11 Correct 31 ms 30976 KB Output is correct
12 Correct 31 ms 30844 KB Output is correct
13 Correct 31 ms 30848 KB Output is correct
14 Correct 31 ms 30848 KB Output is correct
15 Correct 31 ms 30848 KB Output is correct
16 Correct 30 ms 30848 KB Output is correct
17 Correct 33 ms 31480 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 30848 KB Output is correct
2 Correct 30 ms 30848 KB Output is correct
3 Correct 2106 ms 761488 KB Output is correct
4 Correct 1269 ms 244284 KB Output is correct
5 Correct 765 ms 182216 KB Output is correct
6 Correct 676 ms 158752 KB Output is correct
7 Correct 770 ms 182908 KB Output is correct
8 Runtime error 2000 ms 1048584 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 60536 KB Output is correct
2 Runtime error 2165 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 60536 KB Output is correct
2 Runtime error 2165 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 30848 KB Output is correct
2 Correct 31 ms 30848 KB Output is correct
3 Correct 31 ms 30976 KB Output is correct
4 Correct 31 ms 30840 KB Output is correct
5 Correct 32 ms 31224 KB Output is correct
6 Correct 32 ms 31232 KB Output is correct
7 Correct 34 ms 31232 KB Output is correct
8 Correct 32 ms 31096 KB Output is correct
9 Correct 31 ms 30848 KB Output is correct
10 Correct 33 ms 31480 KB Output is correct
11 Correct 31 ms 30976 KB Output is correct
12 Correct 31 ms 30844 KB Output is correct
13 Correct 31 ms 30848 KB Output is correct
14 Correct 31 ms 30848 KB Output is correct
15 Correct 31 ms 30848 KB Output is correct
16 Correct 30 ms 30848 KB Output is correct
17 Correct 33 ms 31480 KB Output is correct
18 Correct 30 ms 30848 KB Output is correct
19 Correct 30 ms 30848 KB Output is correct
20 Correct 2106 ms 761488 KB Output is correct
21 Correct 1269 ms 244284 KB Output is correct
22 Correct 765 ms 182216 KB Output is correct
23 Correct 676 ms 158752 KB Output is correct
24 Correct 770 ms 182908 KB Output is correct
25 Runtime error 2000 ms 1048584 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -