Submission #838391

#	Time	Username	Problem	Language	Result	Execution time	Memory
838391		jasmin	Digital Circuit (IOI22_circuit)	C++17	0 / 100	19 ms	11560 KiB

circuit

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

const int MOD=1e9+2022;

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

vector<vector<int> > pos;

void update_node(int v){

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

    for(auto u: adi[v]){

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

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

            if(0<i){
                cnt[i] += (cnt[i-1]*pos[u][1])%MOD;
                cnt[i]%=MOD;
            }
        }
    }

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

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

    ssum=0;
    for(int i=0; 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;
    adi.assign(n+m, {});
    for(int i=1; i<n+m; i++){

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

    state = a;

    pos.assign(n, vector<int> (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: 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