Submission #1066955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066955		j_vdd16	Digital Circuit (IOI22_circuit)	C++17	7 / 100	3009 ms	3900 KiB

circuit

#include "circuit.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;


int n, m;
vvi children;
vector<signed> assignment;
vi c;

constexpr int mod = 1'000'002'022;
int dfs(int node) { //a
    if (node >= n) {
        return { assignment[node - n] };
    }

    vii counts; //c, a
    for (int child : children[node]) {
        int res = dfs(child);
        counts.push_back({c[child], res});
    }

    /*
    2 children:
    a = 
        1 * (a[0] * b[1] + b[0] * a[1]) +
        2 * (a[0] * a[1])
      =
        1 * (a[0] * (c[1] - a[1]) + (c[0] - a[0]) * a[1]) +
        2 * (a[0] * a[1])
      = a[0] * c[1] + c[0] * a[1]
    */
    /*
    a - b
    |
    c - d
    |
    e

    c = e * 1 + d * 1
    a = c * 1 + b * 2 = (e * 1 + d * 1) + b * 2
    */
    return (counts[0].first * counts[1].second + counts[0].second * counts[1].first) % mod;
}

vi factors;
void cDfs(int node) {
    if (node >= n) {
        c[node] = 1;
        return;
    }

    vii out;
    c[node] = children[node].size();
    for (int child : children[node]) {
        cDfs(child);

        c[node] = (c[node] * c[child]) % mod;
    }
}
void factorDfs(int node, int factor) {
    if (node >= n) {
        factors[node - n] = factor;
        return;
    }

    factorDfs(children[node][0], (factor * c[children[node][1]]) % mod);
    factorDfs(children[node][1], (factor * c[children[node][0]]) % mod);
}

void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
    n = N;
    m = M;
    children = vvi(n);
    assignment = A;
    c = vi(n + m);
    factors = vi(m);

    for (int i = 1; i < n + m; i++) {
        children[P[i]].push_back(i);
    }

    cDfs(0);
    factorDfs(0, 1);
}

signed count_ways(signed L, signed R) {
    for (int i = L; i <= R; i++) {
        assignment[i - n] ^= 1;
    }

    int res = 0;
    loop(i, m) {
        res = (res + assignment[i] * factors[i]) % mod;
    }

    return res;
    /*
    3 children:
    a = 
        1 * (a[0] * b[1] * b[2] + b[0] * a[1] * b[2] + b[0] * b[1] * a[2]) + 
        2 * (a[0] * a[1] * b[2] + a[0] * b[1] * a[2] + b[0] * a[1] * a[2]) +
        3 * (a[0] * a[1] * a[2])
      =
        1 * (a[0] * (c[1] - a[1]) * (c[2] - a[2]))
        2 * (a[0] * a[1] * (c[2] - a[2]))
        3 * (a[0] * a[1] * a[2])
      =
        (1 + 2 - 3) * (a[0] * a[1] * a[2])
        a[0] * c[1] * c[2]
        2 * (a[0] * a[1] * c[2]) - 2 * (a[0] * a[1] * c[2])
    
    C = c[0] * c[1] * c[2] * 3
    b = C - a
      = 

    2 children:
    a = 
        1 * (a[0] * b[1] + b[0] * a[1]) +
        2 * (a[0] * a[1])
      =
        1 * (a[0] * (c[1] - a[1]) + (c[0] - a[0]) * a[1]) +
        2 * (a[0] * a[1])
      = a[0] * c[1] + c[0] * a[1]
    
    C = c[0] * c[1] * 2
    b = C - a
      = 
    */

    //return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 7 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11