Submission #1235812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235812		mariza	Digital Circuit (IOI22_circuit)	C++20	0 / 100	1291 ms	2162688 KiB

circuit

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

typedef long long ll;

ll n, m, a[1000];

vector<ll> t[1000];
pair<ll,ll> dfs(ll curr){
    // cout<<curr<<endl;
    if(curr>=n){
        if(a[curr-n]) return {0,1};
        else return {1,0};
    }
    else{
        ll a0, a1, b0, b1;
        tie(a0,a1)=dfs(t[curr][0]);
        tie(b0,b1)=dfs(t[curr][1]);
        return {2*a0*b0 + a0*b1 + a1*b0, 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);
    }
}

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

• 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