oj.uz

Submission #645354

# Submission time Handle Problem Language Result Execution time Memory
645354 2022-09-26T21:03:40 Z Alex_tz307 Restore Array (RMI19_restore) C++17
7 / 100
 600 ms 772 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 5e3;
const int INF = 1e9;
int n, m, d[1 + kN], cnt[1 + kN];
vector<pair<int, int>> g[1 + kN];
bitset<1 + kN> inQ;

/// Sistem de inecuatii diferentiale peste sumele partiale pe prefix
/// Dupa ce rezolv sistemul pentru sumele partiale obtin simplu si elementele: a[i] = p[i] - p[i - 1]

bool BellmanFord(int s) {
  for (int i = 0; i <= n; ++i) {
    d[i] = INF;
  }
  d[s] = 0;
  queue<int> q;
  q.emplace(s);
  inQ[s] = true;
  cnt[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inQ[u] = false;
    for (const auto &it : g[u]) {
      int v, w;
      tie(v, w) = it;
      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        if (!inQ[v]) {
          if (cnt[v] == n) {
            return true;
          }
          q.emplace(v);
          inQ[v] = true;
          cnt[v] += 1;
        }
      }
    }
  }
  return false;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int l, r, k, v;
    cin >> l >> r >> k >> v;
    r += 1;
    if (v == 0) {
      /// sunt cel putin k valori de 0 in intervalul l..r <=> p[r] - p[l - 1] <= (r - l + 1) - k
      g[l].emplace_back(r, (r - l) - k);
    } else {
      /// sunt cel putin (r - l + 1) - k + 1 valori de in intervalul l..r
      /// <=> p[r] - p[l - 1] >= (r - l + 1) - k + 1 | *(-1)
      /// <=> p[l - 1] - p[r] <= -(r - l + 1) + k - 1
      g[r].emplace_back(l, -(r - l) + k - 1);
    }
  }
  for (int i = 1; i <= n; ++i) {
    /// p[i - 1] <= p[i] <= p[i - 1] + 1

    /// p[i - 1] - p[i] <= 0
    g[i].emplace_back(i - 1, 0);

    /// p[i] - p[i - 1] <= 1
    g[i - 1].emplace_back(i, 1);
  }
  if (BellmanFord(0)) {
    cout << "-1\n";
  } else {
    for (int i = 1; i <= n; ++i) {
      cout << d[i] - d[i - 1] << ' ';
    }
    cout << '\n';
  }
  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 724 KB Output is correct
2 Correct 13 ms 772 KB Output is correct
3 Correct 12 ms 760 KB Output is correct
4 Correct 11 ms 768 KB Output is correct
5 Execution timed out 1083 ms 724 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 724 KB Output is correct
2 Correct 13 ms 772 KB Output is correct
3 Correct 12 ms 760 KB Output is correct
4 Correct 11 ms 768 KB Output is correct
5 Execution timed out 1083 ms 724 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 11 ms 724 KB Output is correct
12 Correct 13 ms 772 KB Output is correct
13 Correct 12 ms 760 KB Output is correct
14 Correct 11 ms 768 KB Output is correct
15 Execution timed out 1083 ms 724 KB Time limit exceeded
16 Halted 0 ms 0 KB -