Submission #790525

#	Time	Username	Problem	Language	Result	Execution time	Memory
790525		borisAngelov	Digital Circuit (IOI22_circuit)	C++17	100 / 100	981 ms	52348 KiB

circuit

#include "circuit.h"

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const long long mod = 1e9 + 2022;

int n, m;

vector<int> g[maxn];

long long contribution[maxn];
long long subtree[maxn];

void dfs(int node, int dep)
{
    if (g[node].empty())
    {
        subtree[node] = 1;
        return;
    }

    subtree[node] = 1LL * (g[node].size());

    for (int i = 0; i < g[node].size(); ++i)
    {
        dfs(g[node][i], dep + 1);
        subtree[node] *= subtree[g[node][i]];
        subtree[node] %= mod;
    }
}

void dfs2(int node, long long from_parent)
{
    if (g[node].empty())
    {
        contribution[node] = from_parent;
        return;;
    }

    vector<long long> preffix(g[node].size() + 5, 1);
    vector<long long> suffix(g[node].size() + 5, 1);

    for (int i = 0; i < g[node].size(); ++i)
    {
        if (i == 0)
        {
            preffix[i] = 1;
        }
        else
        {
            preffix[i] = preffix[i - 1] * subtree[g[node][i - 1]];
            preffix[i] %= mod;
        }
    }

    suffix[g[node].size()] = 1LL;

    for (int i = g[node].size() - 1; i >= 0; --i)
    {
        suffix[i] = (suffix[i + 1] * subtree[g[node][i]]) % mod;
    }

    for (int i = 0; i < g[node].size(); ++i)
    {
        long long product = (preffix[i] * suffix[i + 1]) % mod;

        dfs2(g[node][i], (from_parent * product) % mod);
    }
}

long long preffix[maxn];

long long get_sum(int l, int r)
{
    if (l == 0)
    {
        return preffix[r];
    }

    return (preffix[r] - preffix[l - 1] + mod) % mod;
}

struct segment_tree
{
    struct vertex
    {
        long long sum;
        bool lazy;

        vertex()
        {
            sum = 0;
            lazy = false;
        }

        vertex(long long _sum, bool _lazy)
        {
            sum = _sum;
            lazy = _lazy;
        }
    };

    vertex tree[4 * maxn];

    void push_lazy(int node, int l, int r)
    {
        if (tree[node].lazy == true)
        {
            tree[node].sum = (get_sum(l, r) - tree[node].sum + mod) % mod;

            if (l != r)
            {
                tree[2 * node].lazy = 1 - tree[2 * node].lazy;
                tree[2 * node + 1].lazy = 1 - tree[2 * node + 1].lazy;
            }

            tree[node].lazy = false;
        }
    }

    void update(int node, int l, int r, int ql, int qr)
    {
        push_lazy(node, l, r);

        if (l > qr || r < ql)
        {
            return;
        }

        if (ql <= l && r <= qr)
        {
            tree[node].lazy = true;
            push_lazy(node, l, r);
            return;
        }

        int mid = (l + r) / 2;

        update(2 * node, l, mid, ql, qr);
        update(2 * node + 1, mid + 1, r, ql, qr);

        tree[node].sum = (tree[2 * node].sum + tree[2 * node + 1].sum) % mod;
    }

    void update(int l, int r)
    {
        update(1, 0, m - 1, l, r);
    }
};

segment_tree tree;

void init(int N, int M, vector<int> P, vector<int> A)
{
    n = N;
    m = M;

    for (int i = 1; i < P.size(); ++i)
    {
        g[P[i]].push_back(i);
    }

    dfs(0, 0);
    dfs2(0, 1);

    for (int i = 0; i < m; ++i)
    {
        preffix[i] = contribution[i + n];

        if (i > 0)
        {
            preffix[i] += preffix[i - 1];
        }

        preffix[i] %= mod;
    }

    for (int i = 0; i < m; ++i)
    {
        if (A[i] == 1)
        {
            tree.update(i, i);
        }
    }
}

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

    tree.update(l, r);

    return tree.tree[1].sum;
}

Compilation message (stderr)

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

• 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