Submission #963042

#	Time	Username	Problem	Language	Result	Execution time	Memory
963042		anango	Digital Circuit (IOI22_circuit)	C++17	18 / 100	3076 ms	4952 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]);
    }
}

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);
    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];
    }

}
/*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;
    }
    return su;
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11