oj.uz

Submission #331819

# Submission time Handle Problem Language Result Execution time Memory
331819 2020-11-30T09:47:07 Z AlexPop28 Restore Array (RMI19_restore) C++11
0 / 100
 600 ms 131792 KB 
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

const int INF = (int)1e9 + 10;
    
struct Graph {
  vector<bool> inq;
  vector<int> dist, q;
  vector<vector<pair<int, int>>> adj;
  
  Graph(int n) : inq(n), dist(n, INF), adj(n) {}

  void AddEdge(int from, int to, int cost) {
    adj[from].emplace_back(to, cost);
  }

  vector<int> Solve() {
    q = {0};
    dist[0] = 0;
    inq[0] = true;

    for (int it = 0; it < (int)q.size(); ++it) {
      int node = q[it];
      inq[node] = false;

      for (auto &e : adj[node]) {
        int x, c; tie(x, c) = e;
        if (x == 0) continue;

        if (dist[node] + c < dist[x]) {
          dist[x] = dist[node] + c;
          if (!inq[x]) {
            inq[x] = true;
            q.emplace_back(x);
          }
        }
      }
    }

    return dist;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, m; cin >> n >> m;
  Graph g(1 + n);
  for (int i = 0; i < m; ++i) {
    int l, r, k, val; cin >> l >> r >> k >> val; ++l, ++r;
    if (val == 0) {
      // at most r - l + 1 - k 1s
      k = r - l + 1 - k;
      // pref[r] - pref[l - 1] <= k
      // pref[r] <= pref[l - 1] + k
      g.AddEdge(l - 1, r, k);
    } else {
      // at least k 1s
      // pref[r] - pref[l - 1] >= k
      // pref[l - 1] <= pref[r] - k
      g.AddEdge(r, l - 1, -k);
    }
  }

  for (int i = 1; i <= n; ++i) {
    // pref[i] <= pref[i - 1] + 1
    g.AddEdge(i - 1, i, 1);
    // pref[i] >= pref[i - 1]
    g.AddEdge(i, i - 1, 0);
  }

  auto pref = g.Solve();
  for (int i = 1; i <= n; ++i) {
    cout << pref[i] - pref[i - 1] << " \n"[i == n];
  }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Execution timed out 1097 ms 131792 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2028 KB Output is correct
2 Correct 15 ms 2024 KB Output is correct
3 Correct 16 ms 2024 KB Output is correct
4 Incorrect 15 ms 2048 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2028 KB Output is correct
2 Correct 15 ms 2024 KB Output is correct
3 Correct 16 ms 2024 KB Output is correct
4 Incorrect 15 ms 2048 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Execution timed out 1097 ms 131792 KB Time limit exceeded
4 Halted 0 ms 0 KB -