Submission #631590

#	Time	Username	Problem	Language	Result	Execution time	Memory
631590		alontanay	Digital Circuit (IOI22_circuit)	C++17	2 / 100	772 ms	9060 KiB

circuit

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

using namespace std;
using ll = long long;

const int mxN = 100005;
const int MOD = 1000002022;

int coef[mxN];
vector<int> state;

struct Seg {
    ll val;
    ll sum = 0;
    bool flip = false;
    int l, r, mid;
    Seg *ls, *rs;
    Seg(int l, int r): l(l), r(r), mid((l+r)/2) {
        if(l + 1 < r) {
            ls = new Seg(l,mid);
            rs = new Seg(mid,r);
            sum = (ls->sum + rs->sum)%MOD;
            val = (ls->val + rs->val)%MOD;
        } else {
            sum = coef[l];
            val = (coef[l]*state[l]);
        }
    }
    void push() {
        if(!flip) { return; }
        if(l + 1 < r) {
            ls->flip ^= true;
            rs->flip ^= true;
        }
        flip = false;
        val = (MOD + sum - val)%MOD;
    }
    void update(int a, int b) {
        push();
        if(a >= r || b <= l) { return; }
        if(a <= l && b >= r) {
            flip ^= true;
            push();
            return;
        }
        ls->update(a,b);
        rs->update(a,b);
        val = (ls->val + rs->val)%MOD;
    }
};

ll sub_mul[mxN];
ll ex_mul[mxN];
ll deg[mxN];
vector<int> cs[mxN];

void get_mul(int node) {
    ll mul = deg[node];
    for(int ne : cs[node]) {
        get_mul(ne);
        mul *= sub_mul[ne];
        mul %= MOD;
    }
    sub_mul[node] = mul;
}

void dfs(int node, ll val = 1) {
    vector<ll> muls;
    ll cur_res = val;
    for(int ne: cs[node]) {
        muls.push_back(sub_mul[ne]);
        cur_res *= sub_mul[ne];
        cur_res %= MOD;
    }
    ex_mul[node] = cur_res;
    int sz = muls.size();
    vector<ll> pre(sz+1);
    vector<ll> suf(sz+1);
    pre[0] = 1;
    suf[sz] = 1;
    for(int i = 1; i <= sz; i ++) {
        pre[i] = pre[i-1] * muls[i-1];
        pre[i] %= MOD;
    }
    for(int i = sz - 1; i >= 0; i --) {
        suf[i] = suf[i+1] * muls[i];
        suf[i] %= MOD;
    }
    int idx = 0;
    for(int ne : cs[node]) {
        ll cur_mul = (pre[idx] * suf[idx+1])%MOD;
        dfs(ne,val*cur_mul);
        idx ++;
    }
}

Seg *seg;
int n;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n = N;
    state = A;
    for(int i = 1; i < N; i ++) {
        cs[P[i]].push_back(i);
    }
    for(int i = 1; i < N + M; i ++) {
      deg[P[i]] ++;
    }
    get_mul(0);
    dfs(0);
    for(int i = 0; i < M; i ++) {
        coef[i] = ex_mul[P[N+i]];
    }
    seg = new Seg(0,M);
}

int count_ways(int L, int R) {
    L -= n;
    R -= n;
    seg->update(L,R+1);
    return seg->val;
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 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