제출 #963107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963107		anango	디지털 회로 (IOI22_circuit)	C++17	100 / 100	779 ms	50368 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int MOD=1000002022;
vector<int> allprod; //for each node, product of all threshold totals in subtree of the node
vector<int> subt_values; //for each node, product of all threshold totals not on path from node to root
vector<vector<int>> children;
vector<int> ison;
int dfs2currentprod = 1; //the current product of the dfs2 values   
int curS = 0;
int n,m;

void dfs1(int node) {
    allprod[node] = 1;
    for (int j:children[node]) {
        dfs1(j);
        allprod[node] *= allprod[j];
        allprod[node]%=MOD;
    }
    if (children[node].size()) allprod[node]*=children[node].size();
    allprod[node]%=MOD;
}
void dfs2(int node) {
    //calculate the product of all threshold totals not on the path from node to root, for each leaf
    if (!children[node].size()) {
        subt_values[node] = dfs2currentprod;
        return;
    }
    int oldprod = dfs2currentprod;
    int k=children[node].size();
    vector<int> prefprod(k+1,1); //product of sub product for all children with index<i
    for (int i=1; i<=k; i++) {
        prefprod[i] = prefprod[i-1]*allprod[children[node][i-1]];
        prefprod[i]%=MOD;
    }
    vector<int> suffprod(k+1,1); //product of sub product for all children with index>=i
    for (int i=k-1; i>=0; i--) {
        suffprod[i] = suffprod[i+1]*allprod[children[node][i]];
        suffprod[i]%=MOD;
    }
    /*cout << "DFS " << node << " " << dfs2currentprod;
    for (int i=0; i<k+1; i++) {
        cout << i <<" " << prefprod[i] <<" " << suffprod[i] << endl;
    }*/
    for (int i=0; i<k; i++) {
        int totprod=prefprod[i]*suffprod[i+1];
        totprod%=MOD;
        totprod*=oldprod;
        totprod%=MOD;
        dfs2currentprod = totprod;
        dfs2(children[node][i]);
    }
}
vector<int> prefsums; //prefsums[j] = sum of normal contribution BEFORE j
//so do like prefsums[r+1]-prefsums[l]
int maxn=262144;
int MAXN=maxn;
vector<int> tree;
vector<int> lazy;

int getcont(int tl, int tr) {
   // cout << "jam1" << endl;
    int ans=prefsums[tr+1]-prefsums[tl];
   // cout << "jam2" << endl;
    return ans;
}
void push(int node, int tl, int tr) {
    if (lazy[node]==0) {
        return;
    }
    if (lazy[node]==1) {
        tree[node] = ((getcont(tl,tr)-tree[node])%MOD+MOD)%MOD;
        if (tl<tr) {
            lazy[node*2] ^= lazy[node];
            lazy[node*2+1]^=lazy[node];
        }
        lazy[node] = 0;
    }
    
}
void update(int node, int l, int r, int tl, int tr) {
    //cout << "updating " << node <<" " << l <<" "<<r <<" "<< tl <<" " << tr << endl;
    //flip all bits between l and r inclusive
    push(node,tl,tr);
    if (l>tr || r<tl) {
        return;
    }
    if (l<=tl && tr<=r) {
        //full overlap
        tree[node] = getcont(tl, tr) - tree[node];
        tree[node] += MOD;
        tree[node]%=MOD;
        if (tl<tr) {
            lazy[node*2] ^= 1;
            lazy[node*2+1] ^= 1;
        }
        return;
    }
    int m=(tl+tr)/2;
    update(node*2, l, r, tl, m);
    update(node*2+1, l, r, m+1, tr);
    tree[node] = tree[node*2]+tree[node*2+1];
    tree[node]+=MOD;
    tree[node]%=MOD;
    //cout << node <<" "<< tree[node] << " " << tl <<" "<< tr << endl;
    //cout << node <<" " <<tree[node*2] <<" " << tree[node*2+1] << endl;
    //1113
    //1010
    //0110
    //0000
    return;

}
int query(int node, int l, int r, int tl, int tr) {
    //cout << "querying " << node <<" " << l <<" "<<r <<" "<< tl <<" " << tr << endl;

    push(node,tl,tr);
    if (l>tr || r<tl) {
        return 0;
    }
    if (l<=tl && tr<=r) {
        return tree[node];
    }
    int m=(tl+tr)/2;
    int q1 = query(node*2, l, r, tl, m);
    int q2 = query(node*2+1, l, r, m+1, tr);
    int qsum = q1+q2;
    return qsum%MOD;
}

void init(int32_t N, int32_t M, vector<int32_t> P, vector<int32_t> A) {
    n=N;
    m=M;
    allprod = vector<int>(N+M, 1);
    subt_values = vector<int>(N+M, 1);
    ison = vector<int>(M, 1);
    children=vector<vector<int>>(N+M);
    tree=vector<int>(4*maxn,0);
    lazy=vector<int>(4*maxn,0); //bit
    for (int i=1; i<N+M; i++) {
        children[P[i]].push_back(i);
    }
    dfs1(0);
    dfs2(0);
    /*for (int i=0; i<N+M; i++) {
        cout << i <<" " << allprod[i] << endl;
    }
    for (int i=0; i<N+M; i++) {
        cout << i <<" " << subt_values[i] << endl;
    }*/
    prefsums=vector<int>(MAXN+1, 0);
    prefsums[0] = 0; /*3, 4, [-1, 0, 1, 2, 1, 1, 0], [1, 0, 1, 0]*/
    for (int i=1; i<MAXN+1; i++) {
        //cout << i << endl;
        int sv;
        if (i>M) {
            sv=0;
        }
        else {
            sv=subt_values[i-1+N];
        }
        prefsums[i] = (prefsums[i-1]+sv)%MOD;
    } 
    for (int i=0; i<M; i++) {
        //cout << subt_values[i+N] << " ";
    }
    cout << endl;
    //cout << "after init" << endl;
    for (int i=N; i<N+M; i++) {
        ison[i-N] = A[i-N];
        if (A[i-N]==1) {
            
            update(1, i-N, i-N, 0, maxn-1);
        }
        //cout << i << " " << i-N << endl;
    }
    
    

}
/*3 6 5
-1 0 0 1 1 1 2 2 0
0 0 0 0 0 0
3 8*/
int32_t count_ways(int32_t L, int32_t R) {
   /**for (int i=L; i<=R; i++) {
        ison[i-n] = 1-ison[i-n];
    }
    int su=0;
    for (int i=0; i<m; i++) {
        //cout << i <<" " << subt_values[i+n] << endl;
        su+=ison[i]*subt_values[i+n];
        su%=MOD;
    }*/
    update(1,L-n, R-n, 0, maxn-1);
    int su=query(1, 0, maxn-1, 0, maxn-1);
    return su;
}

• 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