제출 #1235829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235829		mariza	Digital Circuit (IOI22_circuit)	C++20	4 / 100	299 ms	11272 KiB

circuit

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

typedef long long ll;
const ll MOD=1e9+2022;
const ll M=1e5;
const ll NM=2e5;

ll n, m, a[M];

vector<ll> t[NM];
ll ans0[NM], ans1[NM];
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)%MOD;
        ans1[curr]=(a0*b1 + a1*b0 + 2*a1*b1)%MOD;
    }
}

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

    dfs(0,1);
}

int count_ways(int l, int r) {
    a[l-n]^=1;
    dfs(l,0);
    ll curr=l;
    while(curr>0){
        curr=(curr-1)/2;
        dfs(curr,0);
    }
    
    return ans1[0];
}

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