Submission #634593

#	Time	Username	Problem	Language	Result	Execution time	Memory
634593		JeanBombeur	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1137 ms	41288 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;
};

node operator+(node a, node b) {
    return {a.val + b.val >= MOD ? a.val + b.val - MOD : a.val + b.val, a.inv + b.inv >= MOD ? a.inv + b.inv - MOD : a.inv + b.inv, 0};
}

vector <int> Adj[MAX_NODES];

long long Sz[MAX_NODES];

node Tree[2 * SIZE];

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())
        Tree[SIZE + node - nbThresholds] = {0, 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 Push(int node) {
    Tree[node].flag = 0;
    swap(Tree[node].val, Tree[node].inv);
    if (node < SIZE)
        Tree[2 * node].flag ^= 1, Tree[2 * node + 1].flag ^= 1;
    return;
}

void Toggle(int node, int qleft, int qright, int left = 0, int right = SIZE) {
    if (Tree[node].flag)
        Push(node);
    if (qright <= left || right <= qleft)
        return;
    if (qleft <= left && right <= qright)
    {
        Push(node);
        return;
    }
    int mid = (left + right) >> 1;
    Toggle(2 * node, qleft, qright, left, mid);
    Toggle(2 * node + 1, qleft, qright, mid, right);
    Tree[node] = Tree[2 * node] + Tree[2 * node + 1];
    return;
}

void init(int nbNodes, int nbSources, vector <int> Parent, vector <int> States) {
    nbThresholds = nbNodes;
    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(Tree[i + SIZE].val, Tree[i + SIZE].inv);
    }
    for (int i = SIZE - 1; i; i --)
    {
        Tree[i] = Tree[2 * i] + Tree[2 * i + 1];
    }
    return;
}

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

Compilation message (stderr)

circuit.cpp: In function 'void DfsSet(int, long long int)':
circuit.cpp:44:48: warning: narrowing conversion of 'value' from 'long long int' to 'int' [-Wnarrowing]
   44 |         Tree[SIZE + node - nbThresholds] = {0, value, 0};
      |                                                ^~~~~

• 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