Submission #634711

#	Time	Username	Problem	Language	Result	Execution time	Memory
634711		hltk	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1224 ms	33684 KiB

circuit

#include "circuit.h"

#include <iostream>
#include <numeric>
#include <algorithm>
#include <vector>

using namespace std;

const int M = 1'000'002'022;
using i64 = long long;

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

int mul(int a, int b) {
  return i64(a) * b % M;
}

struct Tree {
  vector<int> sum, flip_sum, tag;
  void init(int n) {
    sum.resize(n * 4);
    flip_sum.resize(n * 4);
    tag.resize(n * 4);
  }
  void change(int s, int l, int r, int k, int x) {
    if (r - l == 1) {
      sum[s] = x;
      return;
    }
    push(s);
    int m = (l + r) / 2;
    if (k < m) change(s * 2 + 0, l, m, k, x);
    else change(s * 2 + 1, m, r, k, x);
    sum[s] = add(sum[s * 2], sum[s * 2 + 1]);
    flip_sum[s] = add(flip_sum[s * 2], flip_sum[s * 2 + 1]);
  }
  void flip(int s, int l, int r, int ql, int qr) {
    if (r <= ql || qr <= l) return;
    if (ql <= l && r <= qr) return apply(s);
    push(s);
    int m = (l + r) / 2;
    flip(s * 2 + 0, l, m, ql, qr);
    flip(s * 2 + 1, m, r, ql, qr);
    sum[s] = add(sum[s * 2], sum[s * 2 + 1]);
    flip_sum[s] = add(flip_sum[s * 2], flip_sum[s * 2 + 1]);
  }
  void push(int s) {
    if (tag[s]) {
      apply(s * 2 + 0);
      apply(s * 2 + 1);
      tag[s] = 0;
    }
  }
  void apply(int s) {
    swap(flip_sum[s], sum[s]);
    tag[s] ^= 1;
  }
};

vector<vector<int>> children;
vector<int> a;
vector<int> dp;

int prod_dfs(int u) {
  int prod = children[u].empty() ? 1 : children[u].size();
  for (int v : children[u]) {
    prod = mul(prod, prod_dfs(v));
  }
  dp[u] = prod;
  return prod;
}

vector<int> oth_value;

void dfs(int u, int oth) {
  oth_value[u] = oth;
  vector<int> values{1};
  for (int v : children[u]) {
    values.push_back(dp[v]);
  }
  values.push_back(1);
  reverse(values.begin(), values.end());
  vector<int> rvalues = values;
  partial_sum(values.begin(), values.end(), values.begin(), mul);
  partial_sum(rvalues.rbegin(), rvalues.rend(), rvalues.rbegin(), mul);
  values.pop_back();
  for (int v : children[u]) {
    values.pop_back();
    int value = mul(oth, mul(values.back(), rvalues.back()));
    dfs(v, value);
    rvalues.pop_back();
  }
}

int n, m;

Tree seg;

void init(int n, int m, vector<int> p, vector<int> a) {
  children.resize(n + m);
  for (int i = 1; i < n + m; ++i) {
    children[p[i]].push_back(i);
  }
  dp.assign(n + m, 0);
  oth_value.assign(n + m, 0);
  prod_dfs(0);
  dfs(0, 1);
  ::n = n;
  ::m = m;
  ::a = a;
  seg.init(m);
  for (int i = 0; i < m; ++i) {
    seg.change(1, 0, m, i, oth_value[i + n]);
    if (a[i] == 0) {
      seg.flip(1, 0, m, i, i + 1);
    }
  }
}

int count_ways(int l, int r) {
  l -= n;
  r -= n;
  seg.flip(1, 0, m, l, r + 1);
  return seg.sum[1];
}

• 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