Submission #1069321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069321		mariaclara	Digital Circuit (IOI22_circuit)	C++17	100 / 100	816 ms	22740 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MOD = 1e9 + 2022;
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int n, m;
vector<int> val, tot, a, lazy;
vector<vector<int>> filhos;
vector<ll> seg, sum;

ll calc_tot(int x) {
    if(x >= n) return 1;

    tot[x] = sz(filhos[x]);
    for(int viz : filhos[x]) {
        tot[x] = (tot[x] * calc_tot(viz))%MOD;
    }

    return tot[x];
}

void dfs(int x) {
    ll at = 1;

    if(x >= n) return;
    
    for(auto viz : filhos[x]) {
        val[viz] = (val[x] * at)%MOD;
        if(viz < n) at = (at*tot[viz])%MOD;
    }

    reverse(all(filhos[x]));
    at = 1;

    for(auto viz : filhos[x]) {
        val[viz] = (val[viz] * at)%MOD;
        if(viz < n) at = (at*tot[viz])%MOD;
    }

    for(auto viz : filhos[x]) dfs(viz);
}

void build(int node, int l, int r) {
    if(l == r) {
        seg[node] = val[l+n] * a[l];
        sum[node] = val[l+n];
        return; 
    }

    int mid = (l+r)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    seg[node] = seg[2*node] + seg[2*node+1];
    sum[node] = sum[2*node] + sum[2*node+1];
}

void prop(int node, bool folha) {
    lazy[node] %= 2;
    if(!lazy[node]) return;

    seg[node] = sum[node] - seg[node];
    lazy[node] = 0;

    if(!folha) {
        lazy[2*node]++;
        lazy[2*node+1]++;
    }
}

void update(int node, int l, int r, int p, int q) {
    prop(node, l == r);

    if(r < p or q < l) return;
    if(p <= l and r <= q) {
        lazy[node] = 1;
        prop(node, l == r);
        return;
    }

    int mid = (l+r)/2;
    update(2*node, l, mid, p, q);
    update(2*node+1, mid+1, r, p, q);
    seg[node] = seg[2*node] + seg[2*node+1];
    sum[node] = sum[2*node] + sum[2*node+1];
}

void init(int N, int M, vector<int> P, vector<int> A) {
    val.resize(N+M);
    tot.resize(N);
    filhos.resize(N);
    a = A;
    n = N;
    m = M;
    seg.resize(4*M);
    sum.resize(4*M);
    lazy.resize(4*M);

    for(int i = 1; i < N+M; i++)
        filhos[P[i]].pb(i);

    calc_tot(0);
    val[0] = 1;
    dfs(0);

    build(1, 0, M-1);
}

int count_ways(int L, int R) {
    update(1, 0, m-1, L-n, R-n);
    return seg[1]%MOD;
}

• 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