Submission #1109747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109747		tibinyte	Digital Circuit (IOI22_circuit)	C++17	100 / 100	2233 ms	43852 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  \  ___/|  | \/\  ___/
 \___  >____/\____ |\___  > /____  > |__| (____  /__|   |__| /____  > |___|  /\___  >__|    \___  >
     \/           \/    \/       \/            \/                 \/       \/     \/            \/
*/

struct aint
{
  vector<Mint> a;
  vector<Mint> sp;
  vector<int> lazy;
  aint() {}
  aint(int n, vector<Mint> coef)
  {
    a.resize(4 * n);
    lazy.resize(4 * n);
    sp.push_back(0);
    for (int i = 0; i < n; ++i)
    {
      sp.push_back(sp.back() + coef[i]);
    }
  }
  void prop(int node, int left, int right)
  {
    if (lazy[node])
    {
      a[node] = sp[right] - sp[left - 1] - a[node];
      if (left != right)
      {
        lazy[2 * node] ^= 1;
        lazy[2 * node + 1] ^= 1;
      }
      lazy[node] = 0;
    }
  }
  void update(int node, int left, int right, int st, int dr)
  {
    prop(node, left, right);
    if (right < st || left > dr)
    {
      return;
    }
    if (st <= left && dr >= right)
    {
      lazy[node] ^= 1;
      prop(node, left, right);
      return;
    }
    int mid = (left + right) / 2;
    update(2 * node, left, mid, st, dr);
    update(2 * node + 1, mid + 1, right, st, dr);
    a[node] = a[2 * node] + a[2 * node + 1];
  }
};

int n, m;
aint lesgo;

void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
  n = N + M;
  m = M;
  vector<Mint> coef(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);
  lesgo = aint(m, coef);
  for (int i = 0; i < m; ++i)
  {
    if (A[i])
    {
      lesgo.update(1, 1, m, i + 1, i + 1);
    }
  }
}

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

  lesgo.update(1, 1, m, L, R);
  return lesgo.a[1].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:191:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Mint>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |     for (int i = 1; i < children.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~
circuit.cpp:200:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Mint>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |     for (int i = 0; i < children.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~
circuit.cpp:209:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Mint>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |       if (i != children.size() - 1)
      |           ~~^~~~~~~~~~~~~~~~~~~~~~

• 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