Submission #874186

#	Time	Username	Problem	Language	Result	Execution time	Memory
874186		LucaLucaM	Passport (JOI23_passport)	C++17	48 / 100	716 ms	374780 KiB

passport

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <queue>
#warning That's the baby, that's not my baby

typedef long long ll;

const int NMAX = 2500;

/**

ce cred eu ca se intampla defapt e ca mereu voi putea accesa un interval de tari

si atunci o sa am o dinamica de genu

dp[i][l] =def= care e cel mai din dreapta r la care pot ajunge dupa i operatii, a.i. am capatul din stanga pe pozitia l
asta pare greu de optimizat

dp[l][r] =def= #min de operatii ca sa ajung cu capatul stanga in l si capatul dreapta in r

ok si facem asta gen invers si iese 0-1 bfs

**/

struct Country {
  int l, r;
};

int dist[NMAX * NMAX + 1];

std::vector<std::pair<int, int>> g[NMAX * NMAX + 1];

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

  int n;
  std::cin >> n;
  std::vector<Country> v(n + 1);
  int rMax[n + 1] = {};
  for (int i = 1; i <= n; i++) {
    std::cin >> v[i].l >> v[i].r;
    rMax[i] = std::max(rMax[i - 1], v[i].r);
  }

  std::function<int(int, int)> encode = [&] (int i, int j) -> int {
    return (i - 1) * n + j;
  };

  for (int i = 1; i <= n * n; i++) {
    dist[i] = 1e9;
  }

  dist[encode(1, n)] = 0;

  for (int i = 1; i <= n; i++) {
    int newL = n + 1, newR = 0;
    for (int j = i; j <= n; j++) {
      newL = std::min(newL, v[j].l);
      newR = std::max(newR, v[j].r);
      g[encode(newL, j)].push_back({encode(i, j), 1});
      g[encode(i, newR)].push_back({encode(i, j), 1});
      g[encode(v[i].l, v[i].r)].push_back({encode(i, j), 1});
      if (i != j) {
        g[encode(i + 1, j)].push_back({encode(i, j), 0});
      }
    }
  }

  std::deque<int> deq;
  deq.push_back(encode(1, n));
  while (!deq.empty()) {
    int u = deq.front();
    deq.pop_front();
    for (const auto &[v, c] : g[u]) {
      if (dist[u] + c < dist[v]) {
        if (c == 0) {
          deq.push_front(v);
        } else {
          deq.push_back(v);
        }
        dist[v] = dist[u] + c;
      }
    }
  }

  for (int i = 1; i <= n * n; i++) {
    dist[i] = (dist[i] == 1e9? -1 : dist[i]);
  }

  int Q;
  std::cin >> Q;

  while (Q--) {
    int x;
    std::cin >> x;
    if (x == 1) {
      int answer = 0;
      while (x != n && rMax[x] > x) {
        x = rMax[x];
        answer++;
      }
      if (x != n) {
        answer = -1;
      }
      std::cout << answer << '\n';
    } else {
      std::cout << dist[encode(x, x)] << '\n';
    }
  }

  return 0;
}

Compilation message (stderr)

passport.cpp:8:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    8 | #warning That's the baby, that's not my baby
      |  ^~~~~~~

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