oj.uz

Submission #331822

# Submission time Handle Problem Language Result Execution time Memory
331822 2020-11-30T10:03:38 Z AlexPop28 Restore Array (RMI19_restore) C++11
7 / 100
 600 ms 888 KB 
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

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

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

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

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

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

        if (dist[node] + c < dist[x]) {
          dist[x] = dist[node] + c;
          if (++cnt_push[x] > n) {
            cout << "-1";
            exit(0);
          }

          if (!inq[x]) {
            inq[x] = true;
            q.emplace(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 r - l + 1 - k + 1 1s
      k = r - l + 1 - k + 1;
      // 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
7.0 / 7.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 888 KB Output is correct
2 Correct 16 ms 748 KB Output is correct
3 Correct 16 ms 748 KB Output is correct
4 Correct 14 ms 748 KB Output is correct
5 Execution timed out 855 ms 868 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 888 KB Output is correct
2 Correct 16 ms 748 KB Output is correct
3 Correct 16 ms 748 KB Output is correct
4 Correct 14 ms 748 KB Output is correct
5 Execution timed out 855 ms 868 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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 18 ms 888 KB Output is correct
12 Correct 16 ms 748 KB Output is correct
13 Correct 16 ms 748 KB Output is correct
14 Correct 14 ms 748 KB Output is correct
15 Execution timed out 855 ms 868 KB Time limit exceeded
16 Halted 0 ms 0 KB -