Submission #1055446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055446		spacewalker	Digital Circuit (IOI22_circuit)	C++17	4 / 100	621 ms	10572 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 = right->lazy = true;
      lazy = false;
    }
  }
  CircuitTree() {}
  CircuitTree(int i, int j, const vector<ll> &weights, const vector<int> &init) : total(0), totalFlip(0), al(i), ar(j) {
    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 = true; propagate();
    } else {
      left->flip(i, j); right->flip(i, j);
      combine();
    }
  }
  ll sum() {
    propagate();
    return total;
  }
};

CircuitTree ct;
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);
}

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

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;
      |                     ~~^~~~~~~~~~~~~~~~~~~~

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