Submission #874176

#	Time	Username	Problem	Language	Result	Execution time	Memory
874176		LucaLucaM	Passport (JOI23_passport)	C++17	6 / 100	25 ms	4564 KiB

passport

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

typedef long long ll;

/**

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

**/

struct Country {
  int l, r;
};

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);
  }
  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 {
      int dp[n + 1][n + 1];
      for (int l = 1; l <= n; l++) {
        for (int r = l; r <= n; r++) {
          dp[l][r] = 1e9;
        }
      }
      dp[x][x] = 0;
      for (int l = x; l > 0; l--) {
        for (int r = l; r <= n; r++) {
          for (int j : {l, r}) {
            int newL = std::min(l, v[j].l);
            int newR = std::max(r, v[j].r);
            dp[newL][newR] = std::min(dp[newL][newR], dp[l][r] + 1);
          }
        }
      }
      std::cout << (dp[1][n] == 1e9? -1 : dp[1][n]) << '\n';
    }
  }

  return 0;
}

Compilation message (stderr)

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

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