Submission #634605

#	Time	Username	Problem	Language	Result	Execution time	Memory
634605		JeanBombeur	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1088 ms	42504 KiB

circuit

#include "circuit.h"
#include <vector>
#include <cstdio>
using namespace std;

//  <|°_°|>

//  Jean Bombeur & M. Broccoli

//  The hardest choices require the strongest wills

//  What is better - to be born good, or to overcome your evil nature with great effort ?

const int MOD = (1000002022);
const int MAX_NODES = (2e5);
const int LOG = (17);
const int SIZE = (1 << LOG);

struct node {
    int val = 0, inv = 0, flag = 0;
};

template <class T = int, class F = int>
struct segment_tree {
    vector <T> Tree;
    vector <F> Flags;
    int size = 0, log_max = 0;
    
    // =================== TO FILL ====================
    
    // put here your favorite operation on nodes like min, max, gcd ...
    inline T combine(T left_value, T right_value) {
        return {(left_value.val + right_value.val) % MOD, (left_value.inv + right_value.inv) % MOD, 0};
    }
    
    bool using_lazy = true;  // set to true if you want to enable lazy flags
    
    // put here your favorite operation on flags
    inline F combine_flags(F old_flag, F new_flag) {
        return old_flag ^ new_flag;
    }
    
    bool flags_commute = true;  // set to true if combine_flags is commutative (speeds up a little)
    
    // put here how values and flags interact
    inline T combine_with_flag(T value, F flag) {
        return flag ? (T){value.inv, value.val, 0} : value;
    }
    
    T start_value = {0, 0, 0};  // put here the default value of a node
    T null_value = {0, 0, 0};  // put here the identity value of combine
    F null_flag = 0;  // put here the default value of a flag
    
    // make sure that operator != is defined for flags !
    
    // ================= FOR DEBUG ====================
    
    // put here what you'd like to print about the nodes
    void print_value(T value) {
        printf("%d", value);
        return;
    }
    
    // put here what you'd like to print about the flags
    void print_flag(F flag) {
        printf("%d", flag);
        return;
    }
    
    // ======== DO NOT TOUCH AFTER THIS LINE ==========
    
    // remember to call this at the start !
    // n doesn't need to be a power of two
    void set_to_size(int n) {
        Tree.resize(2 * n, start_value);
        if (using_lazy)
            Flags.resize(n, null_flag);
        size = n;
        log_max = 32 - __builtin_clz(n);
        return;
    }
    
    // destroys everything : ready to be used again !
    void clear() {
        Tree.clear();
        Flags.clear();
        size = log_max = 0;
        return;
    }
    
    // turns an array of exactly size elements into a segtree : equivalent to updating each element but faster
    // void build(vector <T> &Array) {  // you may use this instead
    void build(T* Array) {
        for (int i = 0; i < size; i ++)
            Tree[i + size] = Array[i];
        for (int i = size - 1; i; i --)
            Tree[i] = combine(Tree[i << 1], Tree[(i << 1) ^ 1]);
        return;
    }
    
    // combines flag to node index
    void put_flag(int index, F flag) {
        Tree[index] = combine_with_flag(Tree[index], flag);
        if (index < size)
            Flags[index] = combine_flags(Flags[index], flag);
        return;
    }
    
    // pushes all flags above node index
    void push(int index) {
        for (int h = log_max; h; h --)
        {
            int p = index >> h;
            if (Flags[p] != null_flag)
            {
                put_flag(p << 1, Flags[p]);
                put_flag((p << 1) ^ 1, Flags[p]);
                Flags[p] = null_flag;
            }
        }
        return;
    }
    
    // updates all values above node index
    void pull(int index) {
        for (index >>= 1; index; index >>= 1)
            Tree[index] = combine_with_flag(combine(Tree[index << 1], Tree[(index << 1) ^ 1]), Flags[index]);
        return;
    }
    
    // sets the index-th element to value (zero-based)
    void set(int index, T value) {
        index += size;
        if (using_lazy)
        {
            push(index);
            Tree[index] = value;
            pull(index);
            return;
        }
        Tree[index] = value;
        for (index >>= 1; index; index >>= 1)
            Tree[index] = combine(Tree[index << 1], Tree[(index << 1) ^ 1]);
        return;
    }
    
    // returns the value of the index-th element (zero-based)
    T get(int index) {
        index += size;
        if (using_lazy)
            push(index);
        return Tree[index];
    }
    
    // combines lazily a flag to the range [left, right[  (zero-based)
    void range_add(int left, int right, F flag) {
        left += size, right += size;
        if (!flags_commute)
            push(left), push(right - 1);
        for (int l = left, r = right; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1)
                put_flag(l ++, flag);
            if (r & 1)
                put_flag(-- r, flag);
        }
        pull(left), pull(right - 1);
        return;
    }
    
    // returns combine of all elements in range [left, right[  (zero-based)
    T range_op(int left, int right) {
        left += size, right += size;
        if (using_lazy)
            push(left), push(right - 1);
        T left_ans = null_value, right_ans = null_value;
        for (; left < right; left >>= 1, right >>= 1)
        {
            if (left & 1)
                left_ans = combine(left_ans, Tree[left ++]);
            if (right & 1)
                right_ans = combine(Tree[-- right], right_ans);
        }
        return combine(left_ans, right_ans);
    }
    
    // prints the tree rotated 90 degrees left
    void print(int a = 1, int p = 0) {
        if (a >= 2 * size)
            return;
        if (a == 1)
        {
            for (int i = 0; i < 60; i ++)
                printf("=");
            printf("\n");
        }
        print((a << 1) ^ 1, p + 1);
        for (int i = 0; i < p; i ++)
            printf("\t");
        print_value(Tree[a]);
        if (using_lazy)
        {
            printf(" / ");
            if (a < size)
                print_flag(Flags[a]);
        }
        printf("\n");
        print(a << 1, p + 1);
        if (a == 1)
        {
            for (int i = 0; i < 60; i ++)
                printf("=");
            printf("\n");
        }
        return;
    }
};

vector <int> Adj[MAX_NODES];

long long Sz[MAX_NODES];

segment_tree <node> Segt;
node Sources[MAX_NODES];

int nbThresholds;

int DfsSz(int node) {
    Sz[node] = Adj[node].size() + Adj[node].empty();
    for (int dest : Adj[node])
        Sz[node] *= DfsSz(dest), Sz[node] %= MOD;
    return Sz[node];
}

void DfsSet(int node, long long value) {
    if (Adj[node].empty())
        Sources[node - nbThresholds] = {0, (int)value, 0};
    vector <long long> ProdPref (1, 1);
    vector <long long> ProdSuff (1, 1);
    int sz = Adj[node].size();
    for (int i = 0; i < sz; i ++)
    {
        ProdPref.push_back((ProdPref.back() * Sz[Adj[node][i]]) % MOD);
    }
    for (int i = sz - 1; i >= 0; i --)
    {
        ProdSuff.push_back((ProdSuff.back() * Sz[Adj[node][i]]) % MOD);
    }
    for (int i = 0; i < sz; i ++)
    {
        DfsSet(Adj[node][i], (((value * ProdPref[i]) % MOD) * ProdSuff[sz - i - 1]) % MOD);
    }
    return;
}

void init(int nbNodes, int nbSources, vector <int> Parent, vector <int> States) {
    nbThresholds = nbNodes;
    Segt.set_to_size(nbSources);
    for (int i = 1; i < nbThresholds + nbSources; i ++)
    {
        Adj[Parent[i]].push_back(i);
    }
    DfsSz(0);
    DfsSet(0, 1);
    for (int i = 0; i < nbSources; i ++)
    {
        if (States[i])
            swap(Sources[i].val, Sources[i].inv);
    }
    Segt.build(Sources);
    return;
}

int count_ways(int left, int right) {
    Segt.range_add(left - nbThresholds, (++ right) - nbThresholds, 1);
    return Segt.Tree[1].val;
}

• 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