Submission #1086533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086533		avighna	Passport (JOI23_passport)	C++17	100 / 100	893 ms	148492 KiB

passport

#include <bits/stdc++.h>

typedef long long ll;

const ll inf = 1e15;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n;
  std::cin >> n;
  std::vector<ll> l(n + 1), r(n + 1);
  for (ll i = 1; i <= n; ++i) {
    std::cin >> l[i] >> r[i];
  }

  std::vector<std::vector<std::pair<ll, ll>>> adj(5 * n);

  auto add_edge = [&](ll u, ll v, ll w) { adj[v].push_back({u, w}); };
  std::function<void(ll, ll, ll)> init;
  init = [&](ll v, ll tl, ll tr) {
    if (tl == tr) {
      add_edge(v + n, tl, 0);
      return;
    }
    ll tm = (tl + tr) / 2;
    init(2 * v, tl, tm);
    init(2 * v + 1, tm + 1, tr);
    add_edge(v + n, 2 * v + n, 0);
    add_edge(v + n, 2 * v + 1 + n, 0);
  };
  init(1, 1, n);

  std::function<void(ll, ll, ll, ll)> add;
  add = [&](ll v, ll tl, ll tr, ll i) {
    if (r[i] < tl or tr < l[i]) {
      return;
    }
    if (l[i] <= tl and tr <= r[i]) {
      add_edge(i, v + n, 1);
      return;
    }
    ll tm = (tl + tr) / 2;
    add(2 * v, tl, tm, i);
    add(2 * v + 1, tm + 1, tr, i);
  };
  for (ll i = 1; i <= n; ++i) {
    add(1, 1, n, i);
  }

  auto bfs_0_1 = [&](ll x) {
    std::priority_queue<std::pair<ll, ll>> dq;
    std::vector<bool> vis(5 * n);
    std::vector<ll> dist(5 * n, inf);
    dist[x] = 0;
    dq.push({0, x});
    while (!dq.empty()) {
      auto [d, node] = dq.top();
      dq.pop();
      d *= -1;
      if (vis[node]) {
        continue;
      }
      vis[node] = true;
      for (auto &[i, w] : adj[node]) {
        if (dist[node] + w < dist[i]) {
          dist[i] = dist[node] + w;
          dq.push({-dist[i], i});
        }
      }
    }
    return dist;
  };

  auto a = bfs_0_1(1);
  auto b = bfs_0_1(n);
  for (ll i = 1; i <= n; ++i) {
    if (a[i] != 0) {
      a[i]--;
    }
    if (b[i] != 0) {
      b[i]--;
    }
  }
  std::vector<bool> vis(5 * n);
  std::vector<ll> dist(5 * n, inf);
  std::priority_queue<std::pair<ll, ll>> pq;
  for (ll i = 1; i <= n; ++i) {
    dist[i] = std::min(inf, a[i] + b[i] + 1);
    pq.push({-dist[i], i});
  }
  while (!pq.empty()) {
    auto [d, node] = pq.top();
    pq.pop();
    d *= -1;
    if (vis[node]) {
      continue;
    }
    vis[node] = true;
    for (auto &[i, w] : adj[node]) {
      if (dist[node] + w < dist[i]) {
        dist[i] = dist[node] + w;
        pq.push({-dist[i], i});
      }
    }
  }

  ll q;
  std::cin >> q;
  while (q--) {
    ll x;
    std::cin >> x;
    ll ans = dist[x];
    if (ans == inf) {
      std::cout << "-1\n";
    } else {
      std::cout << ans << '\n';
    }
  }
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46