oj.uz

답안 #874176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
874176 2023-11-16T11:55:59 Z LucaLucaM Passport (JOI23_passport) C++17
6 / 100
 25 ms 4564 KB 
#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

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.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 25 ms 4416 KB Output is correct
5 Correct 24 ms 4444 KB Output is correct
6 Correct 25 ms 4564 KB Output is correct
7 Correct 20 ms 3932 KB Output is correct
8 Correct 17 ms 3336 KB Output is correct

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 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 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 Correct 0 ms 456 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 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 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 Correct 0 ms 456 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# 결과 실행 시간 메모리 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 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 Correct 0 ms 456 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 25 ms 4416 KB Output is correct
5 Correct 24 ms 4444 KB Output is correct
6 Correct 25 ms 4564 KB Output is correct
7 Correct 20 ms 3932 KB Output is correct
8 Correct 17 ms 3336 KB Output is correct
9 Correct 0 ms 344 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 Correct 0 ms 456 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -