Submission #1194033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194033		Ludissey	Digital Circuit (IOI22_circuit)	C++17	100 / 100	367 ms	34788 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;

int N,M;
const int MOD=1e9+2022;
vector<vector<int>> child;
vector<int> p;
vector<int> aP;
vector<int> apR;
vector<int> a;


//SUM
struct node {
    node* left;
    node* right;
    int sum=0;
    int sumoff=0;
    int lazy=0;
    void update(){
        sum=(left->sum+right->sum)%MOD;
        sumoff=(left->sumoff+right->sumoff)%MOD;
    }
};
 
struct segtree {
    int n;
    node* root=new node{nullptr,nullptr,0,0,0};
    void propagate(node* x){
        if(x->lazy%2){
            if(x->left!=NULL) {
                swap(x->left->sum,x->left->sumoff);
                x->left->lazy++;
            }
            if(x->right!=NULL) {
                swap(x->right->sum,x->right->sumoff);
                x->right->lazy++;
            }
            x->lazy++;
        }
    }
    void update(node* x, int l, int r, int qL, int qR){
        if(l>qR||r<qL) return;
        if(l>=qL&&r<=qR){
            x->lazy++;
            swap(x->sum,x->sumoff);
            return;
        }
        propagate(x);
        int mid=(l+r)/2;
        update(x->left,l,mid,qL,qR);
        update(x->right,mid+1,r,qL,qR);
        x->update();
    }
    void build(node* x, int l, int r){
        if(l==r){
            x->sum=(apR[l+N]*a[l+N])%MOD;
            x->sumoff=(apR[l+N]*(1-a[l+N]))%MOD;
            return;
        }
        int mid=(l+r)/2;
        x->left=new node{nullptr,nullptr,0,0,0};
        x->right=new node{nullptr,nullptr,0,0,0};
        build(x->left,l,mid);
        build(x->right,mid+1,r);
        x->update();
    }
    void update(int l, int r){
        update(root,0,n-1,l,r);
    }
    int query(){
        return root->sum;
    }
    void build(int x){
        n=x;
        build(root,0,n-1);
    }
};



int setup_ap(int x){
    if(x>=N) return aP[x]=1;
    aP[x]=1;
    for (auto u : child[x]) aP[x]=(aP[x]*setup_ap(u))%MOD;
    aP[x]=(aP[x]*sz(child[x]))%MOD;
    return (aP[x])%MOD;
}

void setup_apr(int x, int c){
    vector<int> rgt(sz(child[x])+1,1);
    for (int j=sz(child[x])-1; j>=0; j--) {
        rgt[j]=(rgt[j+1]*aP[child[x][j]])%MOD;
    }
    int mP=1;
    apR[x]=c;
    for (int j=0; j<sz(child[x]); j++) {
        int u=child[x][j];
        int v=(rgt[j+1]*mP)%MOD;
        setup_apr(u,(c*v)%MOD);
        mP=(mP*aP[u])%MOD;
    }
    return;
}

segtree seg;
void init(signed n, signed m, std::vector<signed> P, std::vector<signed> A) {
    N=n; M=m;
    p.resize(N+M);
    aP.resize(N+M);
    apR.resize(N+M);
    for (int i = 0; i < N+M; i++) p[i]=P[i];
    child.resize(N+M); a.resize(N+M);
    for (int i = 1; i < N+M; i++) child[P[i]].push_back(i);
    for (int i = N; i < N+M; i++) a[i] = A[i-N];
    setup_ap(0);
    setup_apr(0,1);
    seg.build(M);
}

signed count_ways(signed L, signed R) {
    seg.update(L-N,R-N);
    int sum=seg.query();
    return (int)(sum);
}

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