Submission #1057362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057362		spacewalker	Digital Circuit (IOI22_circuit)	C++17	100 / 100	713 ms	26528 KiB

circuit

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

using namespace std;
using ll = long long;
constexpr ll MOD = 1'000'002'022;

template<class T>
ostream& operator<< (ostream &os, const vector<T> &arr) {
  os << "[";
  for (const T &v : arr) os << v << ", ";
  return os << "]";
}

vector<ll> product_except(vector<ll> nums) {
  int n = nums.size();
  vector<ll> pref = nums, suff = nums;
  for (int i = 1; i < n; ++i) pref[i] = (pref[i-1] * nums[i]) % MOD;
  for (int i = n - 2; i >= 0; --i) suff[i] = suff[i+1] * nums[i] % MOD;
  vector<ll> ans(n);
  for (int i = 0; i < n; ++i) ans[i] = (i > 0 ? pref[i-1] : 1) * (i + 1 < n ? suff[i+1] : 1) % MOD;
  return ans;
}

vector<ll> get_weights(vector<int> P, int M) {
  int N = (int)P.size() - M;
  vector<vector<int>> children(N + M);
  for (int i = 1; i < N + M; ++i) children[P[i]].push_back(i);
  vector<ll> assign_ways(N + M, 1);
  for (int i = N - 1; i >= 0; --i) {
    assign_ways[i] = children[i].size();
    for (int ch : children[i]) assign_ways[i] = (assign_ways[i] * assign_ways[ch]) % MOD;
  }
  vector<ll> ans(N + M, 1);
  for (int i = 0; i < N; ++i) {
    vector<ll> ways_children(children[i].size());
    for (int j = 0; j < children[i].size(); ++j) ways_children[j] = assign_ways[children[i][j]];
    vector<ll> ways_except = product_except(ways_children);
    for (int j = 0; j < children[i].size(); ++j) ans[children[i][j]] = (ans[children[i][j]] * ways_except[j] % MOD * ans[i]) % MOD;
  }
  return vector(begin(ans) + N, end(ans));
}

struct CircuitTree {
  ll total, totalFlip;
  int wt, al, ar;
  bool lazy;
  unique_ptr<CircuitTree> left, right;
  void combine() {
    total = (left->total + right->total) % MOD;
    totalFlip = (left->totalFlip + right->totalFlip) % MOD;
  }
  void propagate() {
    if (lazy) {
      swap(total, totalFlip);
      if (left) {
        left->lazy = !left->lazy;
        right->lazy = !right->lazy;
      }
      lazy = false;
    }
  }
  CircuitTree() {}
  CircuitTree(int i, int j, const vector<ll> &weights, const vector<int> &init) : total(0), totalFlip(0), al(i), ar(j), lazy(false) {
    if (i == j) {
      wt = totalFlip = weights[i];
      if (init[i]) swap(total, totalFlip);
    } else {
      int k = (i + j) / 2;
      left = make_unique<CircuitTree>(i, k, weights, init);
      right = make_unique<CircuitTree>(k + 1, j, weights, init);
      combine();
      // cerr << "[" << i << ", " << j << "] total " << total << " " << totalFlip << endl;
    }
  }
  void flip(int i, int j) {
    propagate();
    if (j < al || ar < i) return;
    if (i <= al && ar <= j) {
      lazy = !lazy; propagate();
    } else {
      left->flip(i, j); right->flip(i, j);
      combine();
    }
  }
  ll sum() {
    propagate();
    return total;
  }
};

struct DumbCircuitTree {
  vector<int> p, a;
  int n, m;
  vector<vector<int>> children;
  DumbCircuitTree() {}
  DumbCircuitTree(vector<int> p, vector<int> a) : p(p), a(a), n((int)p.size() - (int)a.size()), m(a.size()), children(n + m) {
    for (int i = n + m - 1; i > 0; --i) children[p[i]].push_back(i);
  }
  void flip(int L, int R) {
    for (int j = L; j <= R; ++j) a[j] = 1 - a[j];
  }
  bool check_state(vector<int> &thresholds) {
    vector<int> st(n + m);
    for (int i = 0; i < m; ++i) st[i+n] = a[i];
    for (int i = n-1; i >= 0; --i) {
      int active = 0;
      for (int ch : children[i]) if (st[ch] == 1) ++active;
      if (active >= thresholds[i]) st[i] = 1;
    }
    // cerr << thresholds << " " << st << endl;
    return st[0] == 1;
  }
  int _count_ways(vector<int> &thresholds, int i) {
    if (i == n) return check_state(thresholds) ? 1 : 0;
    else {
      int ans = 0;
      for (int ct = 1; ct <= children[i].size(); ++ct) {
        thresholds[i] = ct;
        ans += _count_ways(thresholds, i + 1);
      }
      return ans;
    }
  }
  int count_ways() {
    // cerr << "got ct " << endl;
    vector<int> thresholds(n, 1);
    return _count_ways(thresholds, 0);
  }
};

CircuitTree ct;
DumbCircuitTree dct;
int N;

void init(int _N, int M, std::vector<int> P, std::vector<int> A) {
  N = _N;
  vector<ll> weights = get_weights(P, M); 
  ct = CircuitTree(0, M - 1, weights, A);
  dct = DumbCircuitTree(P, A);
}

int count_ways(int L, int R) {
  ct.flip(L - N, R - N);
  // dct.flip(L - N, R - N);
  return ct.sum();
  // assert(ct.sum() == dct.count_ways());
  // return dct.count_ways();
}

Compilation message (stderr)

circuit.cpp: In function 'std::vector<long long int> get_weights(std::vector<int>, int)':
circuit.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int j = 0; j < children[i].size(); ++j) ways_children[j] = assign_ways[children[i][j]];
      |                     ~~^~~~~~~~~~~~~~~~~~~~
circuit.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int j = 0; j < children[i].size(); ++j) ans[children[i][j]] = (ans[children[i][j]] * ways_except[j] % MOD * ans[i]) % MOD;
      |                     ~~^~~~~~~~~~~~~~~~~~~~
circuit.cpp: In member function 'int DumbCircuitTree::_count_ways(std::vector<int>&, int)':
circuit.cpp:118:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |       for (int ct = 1; ct <= children[i].size(); ++ct) {
      |                        ~~~^~~~~~~~~~~~~~~~~~~~~

• 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