Submission #839149

#	Time	Username	Problem	Language	Result	Execution time	Memory
839149		jasmin	Digital Circuit (IOI22_circuit)	C++17	22 / 100	3089 ms	13648 KiB

circuit

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

const long long MOD=1e9+2022;
//const int INF = INT_MAX;

vector<vector<int> > adi;
vector<int> par;
vector<int> state;

vector<vector<long long> > pos;

void update_node(int v){

    int s=adi[v].size()+1;
    vector<long long> cnt(s);
    cnt[0] = 1;

    for(auto u: adi[v]){

        for(int i=s-1; i>=0; i--){

            cnt[i] *= pos[u][0];
            cnt[i]%=MOD;

            if(0<i){

                long long add = cnt[i-1]*pos[u][1];
                add%=MOD;

                cnt[i] += add;
                cnt[i]%=MOD;
            }
        }
    }

    long long ssum=0ll;
    pos[v][1]=0ll;
    for(int i=s-1; i>=1; i--){
        ssum += cnt[i];
        ssum%=MOD;

        pos[v][1] += ssum;
        pos[v][1] %= MOD;
    }

    ssum=cnt[0];
    pos[v][0]=0ll;
    for(int i=1; i<s; i++){

        pos[v][0] += ssum;
        pos[v][0] %= MOD;

        ssum += cnt[i];
        ssum %= MOD;
    }
}

void init(int n, int m, vector<int> p, vector<int> a) {

    par = p;
    state.assign(n+m, 0);
    for(int i=0; i<m; i++){
        state[n+i] = a[i];
    }

    adi.assign(n, {});
    for(int i=1; i<n+m; i++){

        adi[p[i]].push_back(i);
    }


    pos.assign(n+m, vector<long long> (2, 0));
    for(int i=n; i<n+m; i++){

        pos[i][state[i]] = 1;
    }
    for(int i=n-1; i>=0; i--){
        update_node(i);
    }
}

int count_ways(int L, int R) {
    
    priority_queue<int> pq;
    for(int i=L; i<=R; i++){

        state[i] = 1-state[i];

        pos[i][state[i]] = 1;
        pos[i][1-state[i]] = 0;

        pq.push(par[i]);
    }

    set<int> done;
    while(!pq.empty()){
        int v=pq.top();
        pq.pop();

        if(done.find(v)!=done.end()) continue;
        done.insert(v);

        update_node(v);

        if(par[v]!=-1){
            pq.push(par[v]);
        }
    }

    return pos[0][1];
}

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