oj.uz

Submission #645353

# Submission time Handle Problem Language Result Execution time Memory
645353 2022-09-26T21:03:19 Z Alex_tz307 Restore Array (RMI19_restore) C++17
7 / 100
 600 ms 892 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 - 1) {
            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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 440 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 444 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 852 KB Output is correct
2 Correct 13 ms 892 KB Output is correct
3 Correct 14 ms 848 KB Output is correct
4 Correct 13 ms 852 KB Output is correct
5 Execution timed out 1096 ms 852 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 852 KB Output is correct
2 Correct 13 ms 892 KB Output is correct
3 Correct 14 ms 848 KB Output is correct
4 Correct 13 ms 852 KB Output is correct
5 Execution timed out 1096 ms 852 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 440 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 444 KB Output is correct
11 Correct 12 ms 852 KB Output is correct
12 Correct 13 ms 892 KB Output is correct
13 Correct 14 ms 848 KB Output is correct
14 Correct 13 ms 852 KB Output is correct
15 Execution timed out 1096 ms 852 KB Time limit exceeded
16 Halted 0 ms 0 KB -