Submission #1109743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109743		tibinyte	Digital Circuit (IOI22_circuit)	C++17	22 / 100	3038 ms	8628 KiB

circuit

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

const string asafaciunstringsus = R""""(
So what if you can see the darkest side of me?
No one would ever change this animal I have become
Help me believe it's not the real me
Somebody help me tame this animal
)"""";

typedef long long ll;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int random(int st, int dr)
{
  uniform_int_distribution<int> dist(st, dr);
  return dist(rng);
}

template <typename t>
using ordered_set = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 1000002022;
struct Mint
{
  int val;
  Mint(int x = 0)
  {
    val = (x % mod + mod) % mod;
  }
  Mint(long long x)
  {
    val = x % mod;
  }
  Mint operator+(Mint oth)
  {
    return val + oth.val;
  }
  Mint operator-(Mint oth)
  {
    return val - oth.val + mod;
  }
  Mint operator*(Mint oth)
  {
    return 1ll * val * oth.val;
  }
  void operator+=(Mint oth)
  {
    val = (*this + oth).val;
  }
  void operator-=(Mint oth)
  {
    val = (*this - oth).val;
  }
  void operator*=(Mint oth)
  {
    val = (*this * oth).val;
  }
};

Mint powmod(int a, int b)
{
  if (b == 0)
  {
    return 1;
  }
  if (b % 2 == 1)
  {
    return powmod(a, b - 1) * a;
  }
  Mint p = powmod(a, b / 2);
  return p * p;
}

/*
                 .___                 __                 __           .__
  ____  ____   __| _/____     _______/  |______ ________/  |_  ______ |  |__   ___________   ____
_/ ___\/  _ \ / __ |/ __ \   /  ___/\   __\__  \\_  __ \   __\/  ___/ |  |  \_/ __ \_  __ \_/ __ \
\  \__(  <_> ) /_/ \  ___/   \___ \  |  |  / __ \|  | \/|  |  \___ \  |   Y  \  ___/|  | \/\  ___/
 \___  >____/\____ |\___  > /____  > |__| (____  /__|   |__| /____  > |___|  /\___  >__|    \___  >
     \/           \/    \/       \/            \/                 \/       \/     \/            \/
*/

int n, m;

Mint ans = 0;
vector<Mint> coef;
vector<int> now;

void toggle(int ind)
{
  ans += coef[ind] * (now[ind] == 0 ? 1 : -1);
  now[ind] ^= 1;
}

void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
  n = N + M;
  m = M;
  coef.resize(m);
  now.resize(m);
  vector<vector<int>> g(n);
  for (int i = 1; i < n; ++i)
  {
    g[P[i]].push_back(i);
  }

  vector<Mint> prod(n);

  function<void(int)> dfs_prod = [&](int node)
  {
    if (g[node].empty())
    {
      prod[node] = 1;
      return;
    }
    prod[node] = (int)g[node].size();
    for (auto it : g[node])
    {
      dfs_prod(it);
      prod[node] *= prod[it];
    }
  };
  dfs_prod(0);

  vector<Mint> ans(n, 1);

  function<void(int)> dfs = [&](int node)
  {

    if (g[node].empty())
    {
      coef[node - N] = ans[node];
      return;
    }

    vector<Mint> children;

    for (auto it : g[node])
    {
      children.push_back(prod[it]);
    }

    vector<Mint> prefprod(children.size()), sufprod(children.size());

    prefprod[0] = children[0];
    sufprod.back() = children.back();
    for (int i = 1; i < children.size(); ++i)
    {
      prefprod[i] = prefprod[i - 1] * children[i];
    }
    for (int i = children.size() - 2; i >= 0; --i)
    {
      sufprod[i] = sufprod[i + 1] * children[i];
    }

    for (int i = 0; i < children.size(); ++i)
    {
      int it = g[node][i];

      ans[it] = ans[node];
      if (i != 0)
      {
        ans[it] *= prefprod[i - 1];
      }
      if (i != children.size() - 1)
      {
        ans[it] *= sufprod[i + 1];
      }

      dfs(it);
    }
  };
  dfs(0);
  for (int i = 0; i < m; ++i)
  {
    if (A[i])
    {
      toggle(i);
    }
  }
}

int count_ways(int L, int R)
{
  L -= n - m;
  R -= n - m;

  for (int i = L; i <= R; ++i)
  {
    toggle(i);
  }
  return ans.val;
}

/*
I cannot take this anymore
Saying everything I've said before
All these words, they make no sense
I find bliss in ignorance
Less I hear, the less you say
You'll find that out anyway
Just like before

Everything you say to me
(Takes me one step closer to the edge)
(And I'm about to break)
I need a little room to breathe
(Cause I'm one step closer to the edge)
(I'm about to break)
*/

Compilation message (stderr)

circuit.cpp: In lambda function:
circuit.cpp:153:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Mint>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for (int i = 1; i < children.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~
circuit.cpp:162:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Mint>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |     for (int i = 0; i < children.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~
circuit.cpp:171:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Mint>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |       if (i != children.size() - 1)
      |           ~~^~~~~~~~~~~~~~~~~~~~~~

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