Submission #963078

# Submission time Handle Problem Language Result Execution time Memory
963078 2024-04-14T13:27:34 Z anango Digital Circuit (IOI22_circuit) C++17
0 / 100
36 ms 43232 KB
#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) {
    return prefsums[tr+1]-prefsums[tl];
}
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
    if (l>r) {
        return;
    }
    if (l>tr || r<tl) {
        return;
    }
    push(node,tl,tr);
    if (l<=tl && tr<=r) {
        //full overlap
        tree[node] = getcont(tl, tr) - tree[node];
        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;
    return;

}
int query(int node, int l, int r, int tl, int tr) {
    //cout << "querying " << node <<" " << l <<" "<<r <<" "<< tl <<" " << tr << endl;
    if (l>r) {
        return 0;
    }
    if (l>tr || r<tl) {
        return 0;
    }
    push(node,tl,tr);
    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;
}

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;
    }*/
    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);
        }
    }
    prefsums=vector<int>(MAXN+1, 0);
    prefsums[0] = 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;
    } 
    

}
/*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;
}
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 18776 KB 4th lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 18776 KB 4th lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 18776 KB 4th lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 43232 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 43232 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 18776 KB 4th lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 18776 KB 4th lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 18776 KB 4th lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -