oj.uz

Submission #281642

# Submission time Handle Problem Language Result Execution time Memory
281642 2020-08-23T09:30:07 Z Vimmer Sky Walking (IOI19_walk) C++14
10 / 100
 3350 ms 1048580 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 8 ms 10112 KB Output is correct
6 Correct 8 ms 9984 KB Output is correct
7 Correct 8 ms 9984 KB Output is correct
8 Correct 8 ms 9984 KB Output is correct
9 Correct 7 ms 9728 KB Output is correct
10 Correct 9 ms 10240 KB Output is correct
11 Correct 7 ms 9728 KB Output is correct
12 Correct 7 ms 9728 KB Output is correct
13 Correct 7 ms 9728 KB Output is correct
14 Correct 7 ms 9728 KB Output is correct
15 Correct 7 ms 9728 KB Output is correct
16 Correct 7 ms 9728 KB Output is correct
17 Correct 9 ms 10240 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 2716 ms 753812 KB Output is correct
4 Correct 1388 ms 222864 KB Output is correct
5 Correct 928 ms 218876 KB Output is correct
6 Correct 847 ms 196024 KB Output is correct
7 Correct 973 ms 219344 KB Output is correct
8 Runtime error 2870 ms 1048576 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 190 ms 42004 KB Output is correct
2 Runtime error 3350 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 190 ms 42004 KB Output is correct
2 Runtime error 3350 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 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 8 ms 10112 KB Output is correct
6 Correct 8 ms 9984 KB Output is correct
7 Correct 8 ms 9984 KB Output is correct
8 Correct 8 ms 9984 KB Output is correct
9 Correct 7 ms 9728 KB Output is correct
10 Correct 9 ms 10240 KB Output is correct
11 Correct 7 ms 9728 KB Output is correct
12 Correct 7 ms 9728 KB Output is correct
13 Correct 7 ms 9728 KB Output is correct
14 Correct 7 ms 9728 KB Output is correct
15 Correct 7 ms 9728 KB Output is correct
16 Correct 7 ms 9728 KB Output is correct
17 Correct 9 ms 10240 KB Output is correct
18 Correct 7 ms 9728 KB Output is correct
19 Correct 7 ms 9728 KB Output is correct
20 Correct 2716 ms 753812 KB Output is correct
21 Correct 1388 ms 222864 KB Output is correct
22 Correct 928 ms 218876 KB Output is correct
23 Correct 847 ms 196024 KB Output is correct
24 Correct 973 ms 219344 KB Output is correct
25 Runtime error 2870 ms 1048576 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -