Submission #1235821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235821		mariza	Digital Circuit (IOI22_circuit)	C++20	0 / 100	6 ms	1384 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n, m, a[1000];

vector<ll> t[2000];
ll ans0[2000], ans1[2000];
void dfs(ll curr, bool upd){
    // cout<<curr<<endl;
    if(curr>=n){
        ans0[curr]=(a[curr-n]==0);
        ans1[curr]=(a[curr-n]==1);
    }
    else{
        if(upd){
            dfs(t[curr][0],1);
            dfs(t[curr][1],1);
        }
        ll a0, a1, b0, b1;
        a0=ans0[t[curr][0]];
        a1=ans1[t[curr][0]];
        b0=ans0[t[curr][1]];
        b1=ans1[t[curr][1]];
        // cout<<curr<<" "<<2*a0*b0 + a0*b1 + a1*b0<<" "<<a0*b1 + a1*b0 + 2*a1*b1<<endl;
        ans0[curr]=2*a0*b0 + a0*b1 + a1*b0;
        ans1[curr]=a0*b1 + a1*b0 + 2*a1*b1;
    }
}

void init(int N, int M, vector<int> P, vector<int> A) {
    n=N;
    m=M;
    for(ll i=0; i<m; i++){
        a[i]=A[i];
    }
    for(ll i=1; i<n+m; i++){
        t[P[i]].push_back(i);
    }

    for(ll i=0; i<n; i++){
        assert(t[i].size()==2);
    }
}

int count_ways(int l, int r) {
    for(ll i=l-n; i<=r-n; i++){
        a[i]^=1;
    }
    dfs(0,1);
    return ans1[0];
}

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