oj.uz

Submission #627209

# Submission time Handle Problem Language Result Execution time Memory
627209 2022-08-12T11:20:40 Z model_code Digital Circuit (IOI22_circuit) C++17
18 / 100
 2500 ms 5060 KB 
// time_limit/solution-hocky-quadratic-dp.cpp
#include "circuit.h"

#include <bits/stdc++.h>
using namespace std;

const int kMod = (int) 1e9 + 2022;

struct Tree {
  int n, m;
  vector<int> parent, is_on;
  vector<vector<int>> edge;
  vector<int> memo[2];

  Tree(int n_init, int m_init, vector<int> parent_init, vector<int> on_init) :
    n(n_init),
    m(m_init),
    parent(parent_init),
    is_on(on_init),
    edge(n + m) {

    reverse(is_on.begin(), is_on.end());
    is_on.resize(n + m);
    reverse(is_on.begin(), is_on.end());

    for (int i = 1; i < n + m; i++) {
      edge[parent[i]].push_back(i);
    }

    memo[0].resize(n + m, -1);
    memo[1].resize(n + m, -1);

  }

  bool is_leaf(int pos) {
    return pos >= n;
  }

  void toggle(pair<int, int> toggle_bounds) {
    for (int i = toggle_bounds.first; i <= toggle_bounds.second; i++) {
      is_on[i] ^= 1;
    }
  }

  void reset_memo() {
    memo[0].assign(n + m, 0);
    memo[1].assign(n + m, 0);
  }

  int dp(int pos, int intend) {
    return memo[intend][pos];
  }

  void dp(int pos) {

    if (is_leaf(pos)) {
      memo[is_on[pos]][pos] = 1;
      memo[!is_on[pos]][pos] = 0;
      return;
    }

    for (const auto &nx : edge[pos]) dp(nx);

    int child_size = edge[pos].size();
    vector<int> knapsack(1, 1);


    for (const auto &nx : edge[pos]) {

      int current_size = knapsack.size();
      knapsack.push_back(0);


      for (int i = current_size; i >= 0; i--) {
        knapsack[i] = 1LL * knapsack[i] * dp(nx, 0) % kMod;
        if(i - 1 >= 0) knapsack[i] += 1LL * knapsack[i - 1] * dp(nx, 1) % kMod;
        knapsack[i] %= kMod;
      }
    }


    for (int i = 1; i <= child_size; i++) knapsack[i] = (knapsack[i] + knapsack[i - 1]) % kMod;

    auto _get_sum = [&](int l, int r) -> int {
      int return_value = knapsack[r] + kMod;
      if (l > 0) return_value -= knapsack[l - 1];
      if (return_value >= kMod) return_value -= kMod;
      return return_value;
    };

    for (int i = 1; i <= child_size; i++) {
      memo[1][pos] = (memo[1][pos] + _get_sum(i, child_size)) % kMod;
      memo[0][pos] = (memo[0][pos] + _get_sum(0, i - 1)) % kMod;
    }
  }
};

Tree *solution;

void init(int N, int M, vector<int> P, vector<int> A) {
  solution = new Tree(N, M, P, A);
}

int count_ways(int L, int R) {
  solution->reset_memo();
  solution->toggle({L, R});
  solution->dp(0);
  return solution->dp(0, 1);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 14 ms 336 KB Output is correct
4 Correct 17 ms 364 KB Output is correct
5 Correct 22 ms 336 KB Output is correct
6 Correct 20 ms 368 KB Output is correct
7 Correct 23 ms 336 KB Output is correct
8 Correct 19 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 3 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 2 ms 500 KB Output is correct
12 Correct 2 ms 336 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 14 ms 336 KB Output is correct
4 Correct 17 ms 364 KB Output is correct
5 Correct 22 ms 336 KB Output is correct
6 Correct 20 ms 368 KB Output is correct
7 Correct 23 ms 336 KB Output is correct
8 Correct 19 ms 376 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 3 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 2 ms 464 KB Output is correct
19 Correct 2 ms 500 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 336 KB Output is correct
26 Correct 2 ms 336 KB Output is correct
27 Correct 2 ms 336 KB Output is correct
28 Correct 2 ms 336 KB Output is correct
29 Correct 24 ms 384 KB Output is correct
30 Correct 31 ms 384 KB Output is correct
31 Correct 2 ms 464 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 2 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 2 ms 464 KB Output is correct
37 Correct 23 ms 464 KB Output is correct
38 Correct 22 ms 464 KB Output is correct
39 Correct 2 ms 336 KB Output is correct
40 Correct 2 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 336 KB Output is correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3077 ms 5060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3077 ms 5060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 3 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 2 ms 500 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Execution timed out 3077 ms 5060 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 14 ms 336 KB Output is correct
4 Correct 17 ms 364 KB Output is correct
5 Correct 22 ms 336 KB Output is correct
6 Correct 20 ms 368 KB Output is correct
7 Correct 23 ms 336 KB Output is correct
8 Correct 19 ms 376 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 3 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 2 ms 464 KB Output is correct
19 Correct 2 ms 500 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 336 KB Output is correct
26 Correct 2 ms 336 KB Output is correct
27 Correct 2 ms 336 KB Output is correct
28 Correct 2 ms 336 KB Output is correct
29 Correct 24 ms 384 KB Output is correct
30 Correct 31 ms 384 KB Output is correct
31 Correct 2 ms 464 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 2 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 2 ms 464 KB Output is correct
37 Correct 23 ms 464 KB Output is correct
38 Correct 22 ms 464 KB Output is correct
39 Correct 2 ms 336 KB Output is correct
40 Correct 2 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 336 KB Output is correct
43 Execution timed out 3061 ms 720 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 14 ms 336 KB Output is correct
4 Correct 17 ms 364 KB Output is correct
5 Correct 22 ms 336 KB Output is correct
6 Correct 20 ms 368 KB Output is correct
7 Correct 23 ms 336 KB Output is correct
8 Correct 19 ms 376 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 3 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 2 ms 464 KB Output is correct
19 Correct 2 ms 500 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 336 KB Output is correct
26 Correct 2 ms 336 KB Output is correct
27 Correct 2 ms 336 KB Output is correct
28 Correct 2 ms 336 KB Output is correct
29 Correct 24 ms 384 KB Output is correct
30 Correct 31 ms 384 KB Output is correct
31 Correct 2 ms 464 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 2 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 2 ms 464 KB Output is correct
37 Correct 23 ms 464 KB Output is correct
38 Correct 22 ms 464 KB Output is correct
39 Correct 2 ms 336 KB Output is correct
40 Correct 2 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 336 KB Output is correct
43 Execution timed out 3077 ms 5060 KB Time limit exceeded
44 Halted 0 ms 0 KB -