제출 #1286621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286621		mihai145	Restore Array (RMI19_restore)	C++20	컴파일 에러	0 ms	0 KiB

restore

#include <iostream>
#include <queue>
#include <vector>

int n, m;
std::vector<std::vector<std::pair<int, int>>> g;
std::vector<int> d;

inline void add_constraint(int a, int b, int k) {
  g[a].emplace_back(b, k);
  //  std::cout << "Add " << a << "---(" << k << ")--->" << b << '\n';
}

bool bellman_ford(int src) {
  std::vector<int> impr(n + 1, 0);
  std::vector<uint_8> inq(n + 1, 0);
  d[src] = 0;
  inq[src] = true;

  std::queue<int> q;
  q.push(src);

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inq[u] = false;

    for (auto e : g[u]) {
      int v = e.first;
      int new_cost = d[u] + e.second;

      if (new_cost < d[v]) {
        d[v] = new_cost;
        if (inq[v]) {
          continue;
        }

        q.push(v);
        inq[v] = true;
        impr[v]++;

        if (impr[v] >= n) {
          return false;
        }
      }
    }
  }

  return true;
}

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

  std::cin >> n >> m;

  g.resize(n + 1, std::vector<std::pair<int, int>>{});
  d.resize(n + 1, 1000000);

  for (int i = 1; i <= n; i++) {
    add_constraint(i - 1, i, 0);
    add_constraint(i, i - 1, 1);
  }

  for (int i = 0; i < m; i++) {
    int l, r, k, v;
    std::cin >> l >> r >> k >> v;
    ++l, ++r;

    // v = 0 -> >=k zeroes between l and r <=> <= r-l+1-k ones between l and r
    // v = 1 -> <k zeroes between l and r  <=> > r-l+1-k ones between l and r

    // v = 0 -> partsum(r) - partsum(l - 1) <= r-l+1-k
    // v = 1 -> partsum(r) - partsum(l - 1) > r-l+1-k <=> partsum(l - 1) -
    // partsum(r) < -r+l-1+k <=> partsum(l - 1) - partsum(r) <= -r+l-1+k-1

    if (v == 0) {
      add_constraint(r, l - 1, r - l + 1 - k);
    } else {
      add_constraint(l - 1, r, -r + l - 1 + k - 1);
    }
  }

  if (!bellman_ford(0)) {
    std::cout << -1 << '\n';
    return 0;
  }

  for (int i = 1; i <= n; i++) {
    std::cout << -(d[i] - d[i - 1]) << ' ';
  }
  std::cout << '\n';

  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

restore.cpp: In function 'bool bellman_ford(int)':
restore.cpp:16:15: error: 'uint_8' was not declared in this scope; did you mean 'wint_t'?
   16 |   std::vector<uint_8> inq(n + 1, 0);
      |               ^~~~~~
      |               wint_t
restore.cpp:16:21: error: template argument 1 is invalid
   16 |   std::vector<uint_8> inq(n + 1, 0);
      |                     ^
restore.cpp:16:21: error: template argument 2 is invalid
restore.cpp:16:35: error: expression list treated as compound expression in initializer [-fpermissive]
   16 |   std::vector<uint_8> inq(n + 1, 0);
      |                                   ^
restore.cpp:18:6: error: invalid types 'int[int]' for array subscript
   18 |   inq[src] = true;
      |      ^
restore.cpp:26:8: error: invalid types 'int[int]' for array subscript
   26 |     inq[u] = false;
      |        ^
restore.cpp:34:16: error: invalid types 'int[int]' for array subscript
   34 |         if (inq[v]) {
      |                ^
restore.cpp:39:12: error: invalid types 'int[int]' for array subscript
   39 |         inq[v] = true;
      |            ^