oj.uz

Submission #281570

# Submission time Handle Problem Language Result Execution time Memory
281570 2020-08-23T08:15:17 Z Vimmer Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 55572 KB 
#include "walk.h"
#include <bits/stdc++.h>

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

using namespace std;

vector <pair <int, long long> > g[N];

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

long long dst[N], dob[N];

int idr[205][205];

long long 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);

    for (int j = 0; j < m; j++)
        for (int i = 0; i < n; i++)
        if (y[j] <= h[i] && x[l[j]] <= x[i] && x[i] <= x[r[j]])
            {who[j].pb(i); nums[i].pb(j);}

    int id = 0;

    long long ans = 1e18;

    memset(dst, -1, sizeof(dst));

    priority_queue <pair <long long, int> > qr;

    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++;

          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; qr.push({-y[j], id - 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(qr))
    {
        pair <long long, int> pt = qr.top(); qr.pop();

        if (se.find(pt.S) != se.end()) ans = min(ans, -pt.F + dob[pt.S]);

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

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

            dst[itr.F] = s;

            qr.push({-s, itr.F});
        }
    }

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

	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8192 KB Output is correct
2 Correct 5 ms 8192 KB Output is correct
3 Correct 6 ms 8192 KB Output is correct
4 Correct 7 ms 8192 KB Output is correct
5 Correct 8 ms 8704 KB Output is correct
6 Correct 6 ms 8576 KB Output is correct
7 Correct 6 ms 8576 KB Output is correct
8 Correct 6 ms 8576 KB Output is correct
9 Correct 8 ms 8192 KB Output is correct
10 Correct 7 ms 9088 KB Output is correct
11 Correct 5 ms 8192 KB Output is correct
12 Correct 6 ms 8192 KB Output is correct
13 Correct 5 ms 8192 KB Output is correct
14 Correct 8 ms 8192 KB Output is correct
15 Correct 5 ms 8192 KB Output is correct
16 Correct 6 ms 8192 KB Output is correct
17 Correct 7 ms 8960 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8192 KB Output is correct
2 Correct 5 ms 8192 KB Output is correct
3 Execution timed out 4086 ms 20236 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1604 ms 55572 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 1604 ms 55572 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8192 KB Output is correct
2 Correct 5 ms 8192 KB Output is correct
3 Correct 6 ms 8192 KB Output is correct
4 Correct 7 ms 8192 KB Output is correct
5 Correct 8 ms 8704 KB Output is correct
6 Correct 6 ms 8576 KB Output is correct
7 Correct 6 ms 8576 KB Output is correct
8 Correct 6 ms 8576 KB Output is correct
9 Correct 8 ms 8192 KB Output is correct
10 Correct 7 ms 9088 KB Output is correct
11 Correct 5 ms 8192 KB Output is correct
12 Correct 6 ms 8192 KB Output is correct
13 Correct 5 ms 8192 KB Output is correct
14 Correct 8 ms 8192 KB Output is correct
15 Correct 5 ms 8192 KB Output is correct
16 Correct 6 ms 8192 KB Output is correct
17 Correct 7 ms 8960 KB Output is correct
18 Correct 6 ms 8192 KB Output is correct
19 Correct 5 ms 8192 KB Output is correct
20 Execution timed out 4086 ms 20236 KB Time limit exceeded
21 Halted 0 ms 0 KB -