Submission #1235568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235568		Sir_Ahmed_Imran	Digital Circuit (IOI22_circuit)	C++17	18 / 100	3043 ms	7296 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()

const int mod = 1000002022;

int add(int a, int b){
    return (a + b) % mod;
}

int mul(int a, int b){
    return (1ll * a * b) % mod;
}

int n;
int p[MAXN];
int cnt[MAXN];
int dp[MAXN][2];
vector<int> a[MAXN];

void dfs(int v){
    int N = 0;
    vector<int> cnt {1};
    for(auto & i : a[v]){
        if(i < n) dfs(i);
        cnt.append(0);
        for(int j = N; j >= 0; j--){
            cnt[j + 1] = add(cnt[j + 1], mul(cnt[j], dp[i][1]));
            cnt[j] = mul(cnt[j], dp[i][0]);
        }
        N++;
    }
    dp[v][0] = dp[v][1] = 0;
    for(int i = 0; i <= N; i++){
        dp[v][0] = add(dp[v][0], mul(cnt[i], N - i));
        dp[v][1] = add(dp[v][1], mul(cnt[i], i));
        cnt[i] = 0;
    }
}

void init(int N, int M, vector<int> P, vector<int> A) {
    n = N;
    for(int i = 1; i < P.size(); i++){
        p[i] = P[i];
        a[p[i]].append(i);
    }
    for(int i = 0; i < M; i++)
        dp[i + n][A[i]] = 1;
    cnt[0] = 1;
}

int count_ways(int l, int r){
    for(int i = l; i <= r; i++)
        swap(dp[i][0], dp[i][1]);
    dfs(0);
    return dp[0][1];
}

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