Submission #1246883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246883		rtri	Sky Walking (IOI19_walk)	C++20	10 / 100	4091 ms	16840 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

int n;
vector<vector<int>> adj;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r,
                vector<int> y, int s, int g) {

  map<int, vector<int>> bridge_by_y;
  for (int i = 0; i < y.size(); i++) {
    if (!bridge_by_y.count(y[i]))
      bridge_by_y[y[i]] = vector<int>();
    bridge_by_y[y[i]].push_back(i);
  }

  priority_queue<tuple<ll, ll, ll>> que;
  que.push({0, s, 0});
  map<pair<ll, ll>, ll> dists;
  while (que.size()) {
    auto [dist, building, height] = que.top();
    que.pop();
    dist *= -1;
    if (dists.count({building, height}) && dists[{building, height}] < dist)
      continue;

    for (int i = 0; i < l.size(); i++)
      if (l[i] <= building && building <= r[i] && y[i] <= h[building]) {
        ll new_dist = dist + abs(height - y[i]);
        if (!dists.count({building, y[i]}) ||
            new_dist < dists[{building, y[i]}]) {
          dists[{building, y[i]}] = new_dist;
          que.push({-new_dist, building, y[i]});
        }
      }

    if (!bridge_by_y.count(height))
      continue;

    for (int bridge : bridge_by_y[height]) {
      if (!(l[bridge] <= building && building <= r[bridge]))
        continue;
      for (int build = l[bridge]; build <= r[bridge]; build++) {
        if (y[bridge] > h[build])
          continue;

        ll new_dist = dist + abs(x[build] - x[building]);
        if (!dists.count({build, height}) ||
            new_dist < dists[{build, height}]) {
          dists[{build, height}] = new_dist;
          que.push({-new_dist, build, height});
        }
      }
    }
  }

  ll ans = -1;
  for (auto [key, dist] : dists) {
    auto [building, height] = key;
    if (building == g)
      if (ans == -1 || dist + height < ans)
        ans = dist + height;
  }

  return ans;
}

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