Submission #684526

#	Time	Username	Problem	Language	Result	Execution time	Memory
684526		79brue	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1200 ms	41304 KiB

circuit

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

using namespace std;

typedef long long ll;
const ll MOD = 1'000'002'022;

int n, m;

struct segTree{
    ll sum[800002], rev[800002], lazy[800002];

    void init(int i, int l, int r, ll *A, vector<int> &B){
        lazy[i] = 0;
        if(l==r){
            sum[i] = A[l], rev[i] = 0;
            if(!B[l-n]) swap(sum[i], rev[i]);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A, B);
        init(i*2+1, m+1, r, A, B);
        sum[i] = (sum[i*2] + sum[i*2+1]) % MOD;
        rev[i] = (rev[i*2] + rev[i*2+1]) % MOD;
    }

    void propagate(int i, int l, int r){
        if(!lazy[i]) return;
        swap(sum[i], rev[i]);
        if(l!=r) lazy[i*2] = !lazy[i*2], lazy[i*2+1] = !lazy[i*2+1];
        lazy[i] = 0;
    }

    ll query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return 0;
        if(s<=l && r<=e) return sum[i];
        int m = (l+r)>>1;
        return (query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e)) % MOD;
    }

    void update(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] = 1;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e), update(i*2+1, m+1, r, s, e);
        sum[i] = (sum[i*2] + sum[i*2+1]) % MOD;
        rev[i] = (rev[i*2] + rev[i*2+1]) % MOD;
    }
} tree;

int par[200002];
vector<int> link[200002];
ll S[200002], W[200002];

void dfs(int x){
    S[x] = max(1, (int)link[x].size());
    for(auto y: link[x]){
        dfs(y);
        S[x] = (S[x] * S[y]) % MOD;
    }
}

void dfs2(int x, ll up = 1){
    int k = (int)link[x].size();
    vector<ll> prf(k+1), suf(k+1);
    prf[0] = suf[k] = 1;
    for(int i=1; i<=k; i++) prf[i] = (prf[i-1] * S[link[x][i-1]]) % MOD;
    for(int i=k-1; i>=0; i--) suf[i] = (suf[i+1] * S[link[x][i]]) % MOD;

    W[x] = up;
    for(int i=0; i<k; i++){
        dfs2(link[x][i], up * prf[i] % MOD * suf[i+1] % MOD);
    }
}

void init(int _n, int _m, vector<int> P, vector<int> A){
    n = _n, m = _m;
    for(int i=0; i<n+m; i++) par[i] = P[i], link[par[i]].push_back(i);
    dfs(0);
    dfs2(0);
    tree.init(1, n, n+m-1, W, A);
}

int count_ways(int L, int R) {
    tree.update(1, n, n+m-1, L, R);
    return tree.query(1, n, n+m-1, n, n+m-1);
}

• 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