oj.uz

Submission #1034303

# Submission time Handle Problem Language Result Execution time Memory
1034303 2024-07-25T11:59:11 Z Mr_Husanboy Digital Circuit (IOI22_circuit) C++17
16 / 100
 898 ms 9044 KB 
#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long
const int mod = 1000002022;

vector<int> state, p;
int n, m; 
vector<vector<int>> g;
template<typename T>
int len(T &a){return a.size();}


vector<array<ll, 2>> dp;
vector<int> marked;

void build(int i){
  if(i >= n){
    dp[i][0] = state[i - n] ^ 1;
    dp[i][1] = state[i - n];
    return;
  }
  for(auto u : g[i]) build(u);
  vector<ll> prep(len(g[i]) + 1);
  prep[0] = 1;
  ll al = len(g[i]);
  int cur = 0;
  for(auto u : g[i]){
    cur ++;
    al = al * (dp[u][0] + dp[u][1]) % mod;
    for(int j = cur; j >= 0; j --){
      prep[j] = prep[j] * dp[u][0] % mod;
      if(j) prep[j] += prep[j - 1] * dp[u][1] % mod;
    }
  }
  dp[i][1] = 0;
  for(int j = 1; j <= len(g[i]); j ++){
    dp[i][1] = (dp[i][1] + prep[j] * j) % mod;
  }

  dp[i][0] = al - dp[i][1];
  if(dp[i][0] < 0) dp[i][0] += mod;
}

void push(int i){
  if(!marked[i]) return;
  marked[i] ^= 1;
  int l = g[i][0], r = g[i][1];
  swap(dp[l][0], dp[l][1]);
  swap(dp[r][0], dp[r][1]);
  marked[l] ^= 1;
  marked[r] ^= 1;
}

void upd(int i, int l, int r, int ql, int qr){
  if(l > qr || ql > r) return;
  if(ql <= l && r <= qr){
    swap(dp[i][0], dp[i][1]);
    marked[i] ^= 1;
    return;
  }
  push(i);
  int m = (l + r) / 2;
  upd(g[i][0], l, m, ql, qr);
  upd(g[i][1], m + 1, r, ql, qr);
  vector<ll> prep(len(g[i]) + 1);
  prep[0] = 1;
  ll al = len(g[i]);
  int cur = 0;
  for(auto u : g[i]){
    cur ++;
    al = al * (dp[u][0] + dp[u][1]) % mod;
    for(int j = cur; j >= 0; j --){
      prep[j] = prep[j] * dp[u][0] % mod;
      if(j) prep[j] += prep[j - 1] * dp[u][1] % mod;
    }
  }
  dp[i][1] = 0;
  for(int j = 1; j <= len(g[i]); j ++){
    dp[i][1] = (dp[i][1] + prep[j] * j) % mod;
  }

  dp[i][0] = al - dp[i][1];
  if(dp[i][0] < 0) dp[i][0] += mod;
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
  n = N, m = M;
  g.resize(n);
  state = A;
  p = P;
  for(int i = 1; i < n + m; i ++){
    g[p[i]].push_back(i);
  }
  dp.resize(n + m);
  marked.resize(n + m);
  build(0);

}


int count_ways(int l, int r){
  upd(0, n, n + m - 1, l, r);
  return dp[0][1];
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 2 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Runtime error 1 ms 600 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 2 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 4696 KB Output is correct
2 Correct 746 ms 8792 KB Output is correct
3 Correct 743 ms 8792 KB Output is correct
4 Correct 692 ms 9044 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 4696 KB Output is correct
2 Correct 746 ms 8792 KB Output is correct
3 Correct 743 ms 8792 KB Output is correct
4 Correct 692 ms 9044 KB Output is correct
5 Correct 649 ms 4676 KB Output is correct
6 Correct 865 ms 8792 KB Output is correct
7 Correct 898 ms 8792 KB Output is correct
8 Correct 784 ms 8792 KB Output is correct
9 Correct 359 ms 852 KB Output is correct
10 Correct 702 ms 856 KB Output is correct
11 Correct 760 ms 856 KB Output is correct
12 Correct 682 ms 856 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Runtime error 1 ms 600 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 2 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 2 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -