Submission #628386

#	Time	Username	Problem	Language	Result	Execution time	Memory
628386		c28dnv9q3	Digital Circuit (IOI22_circuit)	C++17	7 / 100	3091 ms	2097152 KiB

circuit

#include "circuit.h"
#include <vector>
#include <cstdio>

using namespace std;
using ll = long long;

// N ... num threshold gates
// M ... num source gates

vector<int> A;
int N, M;
const int MOD = 1000002022;
vector<vector<int>> tree;

void init(int N, int M, vector<int> P, vector<int> A) {
  ::A = A;
  ::N = N;
  ::M = M;
  tree.resize(N);
  for (int i = 1; i < P.size(); i++)
    tree[P[i]].push_back(i);
}
ll mmod(ll v) {
  return ((v % MOD) + MOD) % MOD;
}

pair<ll,ll> countrec(int i) {
  if (i >= N) {
    if (A[i-N]) return {0, 1};
    else return {1, 0};
  }
  auto x = countrec(tree[i][0]);
  auto y = countrec(tree[i][1]);
  ll v = 0;
  // set 1
  v += x.second * y.first;
  v += x.first * y.second;
  v += x.second * y.second;
  // set 2
  v += x.second * y.second;
  
  ll tot = (x.first + x.second) * (y.first + y.second) * 2;
  // printf("%d -> %lld %lld\n", i, tot-v, v);
  return {mmod(tot-v), mmod(v)};
}

// toggle state of source gates between L and R (inclusive)
// return num distinctive param assignments with gate#0 = 1
int count_ways(int L, int R) {
  for (int i = L; i <= R; i++)
    A[i-N] = 1-A[i-N];
  
  return countrec(0).second;
}

Compilation message (stderr)

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for (int i = 1; i < P.size(); i++)
      |                   ~~^~~~~~~~~~

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