Submission #1086252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086252		avighna	Passport (JOI23_passport)	C++17	6 / 100	277 ms	134012 KiB

passport

#include <bits/stdc++.h>

typedef long long ll;

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(8 * n + 10);

  std::function<void(ll, ll, ll)> init;
  init = [&](ll v, ll tl, ll tr) {
    if (tl == tr) {
      adj[v + n].push_back({tl, 0});
      return;
    }
    ll tm = (tl + tr) / 2;
    init(2 * v, tl, tm);
    init(2 * v + 1, tm + 1, tr);
    adj[v + n].push_back({2 * v + n, 0});
    adj[v + n].push_back({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]) {
      adj[i].push_back({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);
  }

  ll q;
  std::cin >> q;
  while (q--) {
    ll x;
    std::cin >> x;

    std::deque<ll> dq;
    std::vector<bool> vis(8 * n + 10);
    std::vector<ll> dist(8 * n + 10, 1e15);
    dist[x] = 0;
    dq.push_front(x);
    while (!dq.empty()) {
      ll node = dq.front();
      dq.pop_front();
      if (vis[node]) {
        continue;
      }
      vis[node] = true;
      for (auto &[i, w] : adj[node]) {
        if (dist[node] + w < dist[i]) {
          dist[i] = dist[node] + w;
          if (w == 0) {
            dq.push_front(i);
          } else {
            dq.push_back(i);
          }
        }
      }
    }

    ll ans = -1e15;
    for (ll i = 1; i <= n; ++i) {
      ans = std::max(ans, dist[i]);
    }
    if (ans == 1e15) {
      std::cout << "-1\n";
    } else {
      std::cout << ans << '\n';
    }
  }
}

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