Submission #627197

#	Time	Username	Problem	Language	Result	Execution time	Memory
627197		model_code	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1398 ms	33152 KiB

circuit

// correct/solution-ayaze-full.cpp
// O(N + M + Q log M)
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

const int kMod = 1'000'002'022;

struct Node {
  bool lazy;
  int val[2];

  Node(int v0 = 0, int v1 = 0) {
    lazy = false;
    val[0] = v0;
    val[1] = v1;
  }

  void flip() {
    lazy = !lazy;
    swap(val[0], val[1]);
  }

  Node operator +(Node other) const {
    Node ret;
    for (int i = 0 ; i < 2 ; i++) {
      ret.val[i] = (val[i] + other.val[i]) % kMod;
    }
    return ret;
  }
};

struct SegmentTree {
  vector<Node> tree;
  int n;

  SegmentTree() {}
  SegmentTree(vector<pair<int, int>> initial_values) {
    n = initial_values.size();
    tree.resize(4 * n + 5);
    build(1, 0, n-1, initial_values);
  }

  void build(int id, int l, int r, vector<pair<int, int>> &initial_values) {
    if (l == r) {
      pair<int, int> val = initial_values[l];
      tree[id] = Node(val.first, val.second);
    } else {
      int m = (l + r) / 2;
      int chld = id << 1;

      build(chld, l, m, initial_values);
      build(chld+1, m+1, r, initial_values);
      tree[id] = tree[chld] + tree[chld+1];
    }
  }

  void propagate(int id) {
    if (!tree[id].lazy) return;
    for (int i = 0 ; i < 2 ; i++) {
      tree[2*id + i].flip();
    }
    tree[id].lazy = false;
  }

  void update(int l, int r) {
    update(1, 0, n-1, l, r);
  }

  void update(int id, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
      tree[id].flip();
    } else {
      int m = (l + r) / 2;
      int chld = id << 1;

      propagate(id);
      if (x <= m) update(chld, l, m, x, y);
      if (y > m)  update(chld+1, m+1, r, x, y);
      tree[id] = tree[chld] + tree[chld+1];
    }
  }

  int query() {
    return tree[1].val[1];
  }
};

SegmentTree segment_tree;
vector<vector<int>> children;
vector<int> child_muls;
vector<int> contribs;
int N;

void DfsMuls(int v) {
  if (v >= N) {
    child_muls[v] = 1;
    return;
  }

  child_muls[v] = children[v].size();
  for (int nex : children[v]) {
    DfsMuls(nex);
    child_muls[v] = 1ll * child_muls[v] * child_muls[nex] % kMod;
  }
}

void DfsContrib(int v, int current_contrib) {
  if (v >= N) {
    contribs[v-N] = current_contrib;
    return;
  }

  vector<int> prefix_contrib(children[v].size()), suffix_contrib(children[v].size());
  for (int i = 0 ; i < static_cast<int>(children[v].size()) ; i++) {
    prefix_contrib[i] = child_muls[children[v][i]];
    if (i > 0) {
      prefix_contrib[i] = 1ll * prefix_contrib[i] * prefix_contrib[i-1] % kMod;
    }
  }
  for (int i = static_cast<int>(children[v].size())-1 ; i >= 0 ; i--) {
    suffix_contrib[i] = child_muls[children[v][i]];
    if (i+1 < static_cast<int>(children[v].size())) { 
      suffix_contrib[i] = 1ll * suffix_contrib[i] * suffix_contrib[i+1] % kMod;
    }
  }

  for (int i = 0 ; i < static_cast<int>(children[v].size()) ; i++) {
    int nex = children[v][i];
    int new_contrib = current_contrib;
    if (i > 0) {
      new_contrib = 1ll * new_contrib * prefix_contrib[i-1] % kMod;
    }
    if (i+1 < static_cast<int>(children[v].size())) { 
      new_contrib = 1ll * new_contrib * suffix_contrib[i+1] % kMod;
    }

    DfsContrib(nex, new_contrib);
  }
}

void init(int _N, int M, std::vector<int> P, std::vector<int> A) {
  N = _N;
  children.resize(N);
  contribs.resize(M);
  child_muls.resize(N+M);

  for (int i = 1 ; i < static_cast<int>(P.size()) ; i++) {
    children[P[i]].push_back(i);
  }
  DfsMuls(0);
  DfsContrib(0, 1);

  vector<pair<int, int>> initial_values;
  for (int i = 0 ; i < M ; i++) {
    pair<int, int> c = {0, contribs[i]};
    if (A[i] == 0) swap(c.first, c.second);
    initial_values.push_back(c);
  }

  segment_tree = SegmentTree(initial_values);
}

int count_ways(int L, int R) {
  segment_tree.update(L-N, R-N);
  return segment_tree.query();
}

• 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: 11 / 11