Submission #634696

#	Time	Username	Problem	Language	Result	Execution time	Memory
634696		hltk	Digital Circuit (IOI22_circuit)	C++17	46 / 100	3079 ms	4284 KiB

circuit

#include "circuit.h"

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

using namespace std;

// If only one the inputs is turned on, vastaus on tulo kaikista / (tulo polulla olevista)
// If all of the inputs are turned on, vastaus on tulo kaikista.
// If two of the inputs are turned on, vastaus on 2 * tulo kaikista / (tulo poluilla (juureen) olevista)
// If three inputs are turned on, vastaus on 2 * tulo kaikista / (tulo poluilla (juureen) olevista)

// |
// |  all / 1-path
// |
// 1
//

//       |
//       |
//       |
//       x
//      / \
//     /   \       all / 1-path + all / 2-path - all / union + all / union = all / 1-path + all / 2-path
//    /     \      |---------------------------------------|   |----------|
//   1       2                       c_x = 1                      c_x = 2
//
//
//       |
//       |
//       |         all / 1-path + all / 2-path + all / 3-path - all / 12-path - all / 13-path - all / 13-path + all / 123-path
//       x         |-------------------------------------------------------------------------------------------------------------|
//      / \                                                        c_x = 1
//     / | \       all / 12-path + all / 13-path + all / 23-path - all / 123-path * 2
//    /  |  \      |----------------------------------------------------------------|
//   1   2   3                                     c_x = 2
//                 all / 123-path
//                 |------------|
//                    c_x = 3

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

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

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;
}

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;

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);
  oth_value = vector<int>(oth_value.begin() + n, oth_value.end());
  ::n = n;
  ::a = a;
}

int count_ways(int l, int r) {
  l -= n;
  r -= n;
  for (int i = l; i <= r; ++i) {
    a[i] ^= 1;
  }
  int ans = 0;
  for (int i = 0; i < (int) a.size(); ++i) {
    if (a[i]) {
      ans = add(ans, oth_value[i]);
    }
  }
  return ans;
}

Compilation message (stderr)

circuit.cpp:25:1: warning: multi-line comment [-Wcomment]
   25 | //      / \
      | ^

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