Submission #1238565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238565		MarwenElarbi	Digital Circuit (IOI22_circuit)	C++17	0 / 100	6 ms	1364 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int nax=2005;
const int MOD = 1e9 + 2022 ;
vector<int> adj[nax];
int a[nax];
long long dp[2][nax];
int n,m;
void dfs(int x,int p){
    if(adj[x].size()==1&&x!=0){
        if(x<n) dp[0][x]=1;
        else dp[a[x-n+1]][x]=1;
        return;
    }
    pair<int,int> child={-1,-1};
    for(auto u:adj[x]){
        if(u==p) continue;
        if(child.fi==-1) child.fi=u;
        else child.se=u;
        dfs(u,x);
    }
    dp[0][x]+=dp[0][child.fi]*dp[1][child.se]+dp[1][child.fi]*dp[0][child.se]+dp[0][child.fi]*dp[0][child.se]*2;
    dp[1][x]+=dp[0][child.fi]*dp[1][child.se]+dp[1][child.fi]*dp[0][child.se]+dp[1][child.fi]*dp[1][child.se]*2;
    dp[0][x]%=MOD;
    dp[1][x]%=MOD;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A){
    n=N;m=M;
    for (int i = 1; i < M+N; ++i)
    {
        adj[i].push_back(P[i]);
        adj[P[i]].push_back(i);
    }
    for (int i = 0; i < M; ++i)
    {
        a[i]=A[i];
    }
}

int count_ways(int L, int R) {
    memset(dp,0,sizeof dp);
    L-=n;R-=n;
    for (int i = L; i <= R; ++i) a[i]^=1;
    dfs(0,-1);
    return dp[1][0];
}

• 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