oj.uz

Submission #1086260

# Submission time Handle Problem Language Result Execution time Memory
1086260 2024-09-09T21:51:56 Z avighna Passport (JOI23_passport) C++17
0 / 100
 2000 ms 124024 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);
  }

  auto bfs_0_1 = [&](ll x, ll bad) {
    std::deque<ll> dq;
    std::vector<bool> vis(5 * n);
    std::vector<ll> dist(5 * n, 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] and (!(w == 1 and node == bad))) {
          dist[i] = dist[node] + w;
          if (w == 0) {
            dq.push_front(i);
          } else {
            dq.push_back(i);
          }
        }
      }
    }
    return dist;
  };

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

    auto dist = bfs_0_1(x, 0);
    ll max = 0;
    for (ll i = 1; i <= n; ++i) {
      max = std::max(max, dist[i]);
    }
    if (max == ll(1e15)) {
      std::cout << "-1\n";
      continue;
    }

    ll ans = 0;
    for (ll i = 1; i <= n; ++i) {
      //  check if i is necessary
      dist = bfs_0_1(x, i);
      ll max = 0;
      for (ll i = 1; i <= n; ++i) {
        max = std::max(max, dist[i]);
      }
      if (max == ll(1e15)) {
        ans++;
      }
    }
    std::cout << ans << '\n';
  }
}

Subtask #1
0 / 6.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 1 ms 348 KB Output is correct
4 Execution timed out 2099 ms 124024 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.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 1 ms 456 KB Output is correct
4 Correct 1 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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Execution timed out 2099 ms 124024 KB Time limit exceeded
5 Halted 0 ms 0 KB -