제출 #628556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
628556		600Mihnea	디지털 회로 (IOI22_circuit)	C++17	89 / 100	3040 ms	24476 KiB

circuit

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

using namespace std;

typedef long long ll;
const int MOD = 1000002022;

struct Vertex {
  int s0, s1;
};

vector<int> c, now;
int dim, subtract;
vector<Vertex> tree;
vector<int> lazy;

void build(int v, int tl, int tr) {
  lazy[v] = 0;

  if (tl == tr) {
    tree[v].s0 = now[tl] * c[tl];
    tree[v].s1 = (1 - now[tl]) * c[tl];
  } else {
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    tree[v].s0 = tree[2 * v].s0 + tree[2 * v + 1].s0;
    tree[v].s1 = tree[2 * v].s1 + tree[2 * v + 1].s1;
    if (tree[v].s0 >= MOD) tree[v].s0 -= MOD;
    if (tree[v].s1 >= MOD) tree[v].s1 -= MOD;
  }
}

void push(int v, int tl, int tr) {
  if (lazy[v]) {
    swap(tree[v].s0, tree[v].s1);
    if (tl < tr) lazy[2 * v] ^= 1, lazy[2 * v + 1] ^= 1;
    lazy[v] = 0;
  }
}

void op(int v, int tl, int tr, int l, int r) {
  push(v, tl, tr);
  if (tr < l || r < tl) return;
  if (l <= tl && tr <= r) {
    lazy[v] ^= 1;
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  op(2 * v, tl, tm, l, r);
  op(2 * v + 1, tm + 1, tr, l, r);
  tree[v].s0 = tree[2 * v].s0 + tree[2 * v + 1].s0;
  tree[v].s1 = tree[2 * v].s1 + tree[2 * v + 1].s1;
  if (tree[v].s0 >= MOD) tree[v].s0 -= MOD;
  if (tree[v].s1 >= MOD) tree[v].s1 -= MOD;
}

void init(int n, int m, std::vector<int> par, std::vector<int> init) {
  dim = m;
  tree.resize(4 * dim + 7);
  lazy.resize(4 * dim + 7);
  subtract = n;
  c.resize(m, 0);
  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);
      prod[a] = prod[a] * (ll) prod[b] % MOD;
    }
  };
  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) {
          send = send * (ll) prod[g[a][j]] % MOD;
        }
      }
      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);
  build(1, 0, dim - 1);
}

int count_ways(int l, int r) {
  l -= subtract;
  r -= subtract;
  op(1, 0, dim - 1, l, r);
  push(1, 0, dim - 1);
  return tree[1].s0;
}

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