Submission #1194001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194001		Ludissey	Digital Circuit (IOI22_circuit)	C++17	9 / 100	3079 ms	5816 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> a;
vector<int> dp;

int fast_pow(int x, int p){
    if(p==0) return 1;
    if(p==1) return x;
    if(p%2==0){
        int r=fast_pow(x,p/2);
        return (r*r)%MOD;
    }else{
        int r=fast_pow(x,p-1);
        return (r*x)%MOD;
    }
}

int dfs(int x){
    if(x>=N) return (dp[x]=a[x]);
    dp[x]=0;
    int mP=1;
    vector<int> rgt(sz(child[x])+1,1);
    for (int j=sz(child[x])-1; j>=0; j--) {
        dfs(child[x][j]);
        rgt[j]=(rgt[j+1]*aP[child[x][j]])%MOD;
    }
    for (int j=0; j<sz(child[x]); j++) {
        int u=child[x][j];
        dp[x]+=(dp[u]*(rgt[j+1]*mP)%MOD)%MOD;
        dp[x]%=MOD;
        mP=(mP*aP[u])%MOD;
    }
    return dp[x];
}


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]*=sz(child[x]);
    return (aP[x])%MOD;
}

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

signed count_ways(signed L, signed R) {
    for (int i = L; i <= R; i++) a[i] = 1-a[i];
    dp.clear();
    dp.resize(N+M);
    dfs(0);
    return (int)(dp[0])%MOD;
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 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