oj.uz

Submission #1086255

# Submission time Handle Problem Language Result Execution time Memory
1086255 2024-09-09T21:30:33 Z avighna Passport (JOI23_passport) C++17
6 / 100
 295 ms 116420 KB 
#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(5 * n);

  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::priority_queue<std::pair<ll, ll>> dq;
    std::vector<bool> vis(5 * n);
    std::vector<ll> dist(5 * n, 1e15);
    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});
        }
      }
    }

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 295 ms 116420 KB Output is correct
5 Correct 187 ms 69956 KB Output is correct
6 Correct 146 ms 60908 KB Output is correct
7 Correct 121 ms 59588 KB Output is correct
8 Correct 127 ms 66504 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 295 ms 116420 KB Output is correct
5 Correct 187 ms 69956 KB Output is correct
6 Correct 146 ms 60908 KB Output is correct
7 Correct 121 ms 59588 KB Output is correct
8 Correct 127 ms 66504 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -