Submission #799530

#	Time	Username	Problem	Language	Result	Execution time	Memory
799530		JakobZorz	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1075 ms	41472 KiB

circuit

#include"circuit.h"
#include<vector>
#include<iostream>
using namespace std;
typedef long long ll;

const int MOD=1000002022;
const int TREE_SIZE=1<<18;

int parents[200000];
ll sub_mul[200000];
vector<int>children[200000];
int n,m;
ll vals[100000];

struct SegTree{
    vector<int>tree;
    vector<int>tree_val;
    vector<bool>lazy;
    
    void init_tree(int node,int l,int r){
        int m=(l+r)/2;
        if(m==l)
            return;
        
        init_tree(2*node,l,m);
        init_tree(2*node+1,m,r);
        tree[node]=tree[2*node]+tree[2*node+1];
        tree[node]%=MOD;
    }
    
    SegTree(ll*arr,int size){
        tree.resize(2*TREE_SIZE);
        tree_val.resize(2*TREE_SIZE);
        lazy.resize(2*TREE_SIZE);
        for(int i=0;i<size;i++)
            tree[TREE_SIZE+i]=arr[i];
        init_tree(1,0,TREE_SIZE);
    }
    
    int get(){
        return tree_val[1];
    }
    
    void push(int node,int l,int r){
        if(lazy[node]){
            lazy[node]=false;
            tree_val[node]=tree[node]+MOD-tree_val[node];
            tree_val[node]%=MOD;
            if(l<r-1){
                lazy[2*node]=!lazy[2*node];
                lazy[2*node+1]=!lazy[2*node+1];
            }
        }
    }
    
    void toggle(int node,int rl,int rr,int l,int r){
        push(node,l,r);
        
        if(rr<=l||r<=rl)
            return;
        
        if(rl<=l&&r<=rr){
            lazy[node]=true;
            push(node,l,r);
            return;
        }
        
        int m=(l+r)/2;
        toggle(2*node,rl,rr,l,m);
        toggle(2*node+1,rl,rr,m,r);
        
        tree_val[node]=tree_val[2*node]+tree_val[2*node+1];
        tree_val[node]%=MOD;
    }
};

SegTree*segtree;

void dfs2(int node){
    if(children[node].empty()){
        sub_mul[node]=1;
        return;
    }
    
    sub_mul[node]=children[node].size();
    for(int ch:children[node]){
        dfs2(ch);
        sub_mul[node]*=sub_mul[ch];
        sub_mul[node]%=MOD;
    }
}

vector<ll>transform(vector<ll>arr){
    if(arr.size()==1)
        return {1};
    int n=(int)arr.size();
    
    vector<ll>arr1,arr2;
    ll arr1_mul=1,arr2_mul=1;
    for(int i=0;i<n/2;i++){
        arr1.push_back(arr[i]);
        arr1_mul*=arr[i];
        arr1_mul%=MOD;
    }
    for(int i=n/2;i<n;i++){
        arr2.push_back(arr[i]);
        arr2_mul*=arr[i];
        arr2_mul%=MOD;
    }
    
    vector<ll>res1=transform(arr1),res2=transform(arr2);
    
    vector<ll>res;
    for(ll i:res1)
        res.push_back((i*arr2_mul)%MOD);
    for(ll i:res2)
        res.push_back((i*arr1_mul)%MOD);
    
    return res;
}

void dfs3(int node,ll val){
    if(children[node].empty()){
        vals[node-n]=val;
        return;
    }
    
    vector<ll>arr(children[node].size());
    for(int i=0;i<(int)children[node].size();i++)
        arr[i]=sub_mul[children[node][i]];
    vector<ll>res=transform(arr);
    
    for(int i=0;i<(int)children[node].size();i++){
        ll val2=val*res[i];
        val2%=MOD;
        dfs3(children[node][i],val2);
    }
    
    /*for(int ch:children[node]){
        ll val2=val;
        for(int ch2:children[node]){
            if(ch2!=ch){
                val2*=sub_mul[ch2];
                val2%=MOD;
            }
        }
        dfs3(ch,val2);
    }*/
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n=N;
    m=M;
    for(int i=0;i<n+m;i++){
        parents[i]=P[i];
        if(parents[i]!=-1)
            children[parents[i]].push_back(i);
    }
    
    dfs2(0);
    dfs3(0,1);
    
    segtree=new SegTree(vals,m);
    
    for(int i=0;i<(int)A.size();i++)
        if(A[i]==1)
            segtree->toggle(1,i,i+1,0,TREE_SIZE);
}

int count_ways(int L, int R) {
    L-=n;
    R-=n;
    segtree->toggle(1,L,R+1,0,TREE_SIZE);
    
    /*for(int i=0;i<m;i++)
        cout<<active[i]<<" ";
    cout<<"\n";
    for(int i=0;i<m;i++)
        cout<<vals[i]<<" ";
    cout<<"\n";*/
    
    
    return segtree->get();
}

• 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