oj.uz

Submission #1109743

# Submission time Handle Problem Language Result Execution time Memory
1109743 2024-11-07T13:25:31 Z tibinyte Digital Circuit (IOI22_circuit) C++17
22 / 100
 3000 ms 8628 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 1020 KB Output is correct
11 Correct 2 ms 848 KB Output is correct
12 Correct 2 ms 336 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 2 ms 336 KB Output is correct
18 Correct 2 ms 1020 KB Output is correct
19 Correct 2 ms 848 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 2 ms 336 KB Output is correct
26 Correct 2 ms 336 KB Output is correct
27 Correct 2 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 592 KB Output is correct
32 Correct 1 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 336 KB Output is correct
36 Correct 1 ms 848 KB Output is correct
37 Correct 1 ms 848 KB Output is correct
38 Correct 2 ms 848 KB Output is correct
39 Correct 2 ms 336 KB Output is correct
40 Correct 2 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 336 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1278 ms 4432 KB Output is correct
2 Correct 1933 ms 8628 KB Output is correct
3 Correct 1895 ms 8528 KB Output is correct
4 Correct 1828 ms 8528 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1278 ms 4432 KB Output is correct
2 Correct 1933 ms 8628 KB Output is correct
3 Correct 1895 ms 8528 KB Output is correct
4 Correct 1828 ms 8528 KB Output is correct
5 Execution timed out 3015 ms 4432 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 1020 KB Output is correct
11 Correct 2 ms 848 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 1278 ms 4432 KB Output is correct
14 Correct 1933 ms 8628 KB Output is correct
15 Correct 1895 ms 8528 KB Output is correct
16 Correct 1828 ms 8528 KB Output is correct
17 Execution timed out 3015 ms 4432 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 2 ms 336 KB Output is correct
18 Correct 2 ms 1020 KB Output is correct
19 Correct 2 ms 848 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 2 ms 336 KB Output is correct
26 Correct 2 ms 336 KB Output is correct
27 Correct 2 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 592 KB Output is correct
32 Correct 1 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 336 KB Output is correct
36 Correct 1 ms 848 KB Output is correct
37 Correct 1 ms 848 KB Output is correct
38 Correct 2 ms 848 KB Output is correct
39 Correct 2 ms 336 KB Output is correct
40 Correct 2 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 336 KB Output is correct
43 Correct 2137 ms 592 KB Output is correct
44 Correct 2910 ms 848 KB Output is correct
45 Execution timed out 3038 ms 592 KB Time limit exceeded
46 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 2 ms 336 KB Output is correct
18 Correct 2 ms 1020 KB Output is correct
19 Correct 2 ms 848 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 2 ms 336 KB Output is correct
26 Correct 2 ms 336 KB Output is correct
27 Correct 2 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 592 KB Output is correct
32 Correct 1 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 336 KB Output is correct
36 Correct 1 ms 848 KB Output is correct
37 Correct 1 ms 848 KB Output is correct
38 Correct 2 ms 848 KB Output is correct
39 Correct 2 ms 336 KB Output is correct
40 Correct 2 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 336 KB Output is correct
43 Correct 1278 ms 4432 KB Output is correct
44 Correct 1933 ms 8628 KB Output is correct
45 Correct 1895 ms 8528 KB Output is correct
46 Correct 1828 ms 8528 KB Output is correct
47 Execution timed out 3015 ms 4432 KB Time limit exceeded
48 Halted 0 ms 0 KB -