Submission #874187

#	Time	Username	Problem	Language	Result	Execution time	Memory
874187		LucaLucaM	Passport (JOI23_passport)	C++17	54 / 100	694 ms	374672 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;
  };
  if (n <= 2500) {

    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: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 0 / 46