Submission #628548

#	Time	Username	Problem	Language	Result	Execution time	Memory
628548		600Mihnea	Digital Circuit (IOI22_circuit)	C++17	18 / 100	3083 ms	4176 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MOD = 1000002022;

int add(int a, int b) {
  a += b;
  if (a >= MOD) return a - MOD;
  if (a < 0) return a + MOD;
  return a;
}

int mul(int a, int b) {
  return a * (ll) b % MOD;
}

void addup(int &a, int b) {
  a = add(a, b);
}

void mulup(int &a, int b) {
  a = mul(a, b);
}

vector<int> c, now;
int dim, subtract;

void init(int n, int m, std::vector<int> par, std::vector<int> init) {
  dim = m;
  subtract = n;
  c.resize(m, 0);
  ///cout << n << " " << m << " : " << (int) par.size() << " vs " << (int) init.size() << "\n";
  vector<vector<int>> g(n + m);
  vector<int> prod(n + m, 1);
  for (int i = 1; i < n + m; i++) {
    g[par[i]].push_back(i);
  }
  function<void(int)> build1 = [&] (int a) {
    if (g[a].empty()) return;
    prod[a] = (int) g[a].size();
    for (auto &b : g[a]) {
      build1(b);
      mulup(prod[a], prod[b]);
    }
  };
  now = init;
  function<void(int, int)> dfs = [&] (int a, int coef) {
    /// optimize this function
    for (int i = 0; i < (int) g[a].size(); i++) {
      int send = coef;
      for (int j = 0; j < (int) g[a].size(); j++) {
        if (i != j) {
          mulup(send, prod[g[a][j]]);
        }
      }
      dfs(g[a][i], send);
    }
    if (g[a].empty()) {
      assert(n + 0 <= a && a < n + m);
      c[a - n] = coef;
    }
  };
  build1(0);
  dfs(0, 1);
}

int count_ways(int l, int r) {
  l -= subtract;
  r -= subtract;
  assert((int) c.size() == dim);
  assert((int) now.size() == dim);
  assert(0 <= l && l <= r && r < dim);
  for (int j = l; j <= r; j++) {
    now[j] ^= 1;
  }
  int sol = 0;
  for (int j = 0; j < dim; j++) {
    addup(sol, mul(c[j], now[j]));
  }
  return sol;
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11