Submission #745268

#	Time	Username	Problem	Language	Result	Execution time	Memory
745268		doowey	Digital Circuit (IOI22_circuit)	C++17	18 / 100	3050 ms	7044 KiB

circuit

#include <bits/stdc++.h>
#include "circuit.h"

using namespace std;

typedef long long ll;

const int N = (int)2e5 + 10;
const int MOD = (int)1e9 + 2022;
vector<int> T[N];
int dp[N][2];

int add(int x, int y){
    x += y;
    if(x >= MOD) x -= MOD;
    else if(x < 0) x += MOD;
    return x;
}

int mult(int x, int y){
    return (x * 1ll * y) % MOD;
}

void dfs(int u){
    if(T[u].empty()) return;
    int S = 0;
    int W = 1;
    dp[u][0] = 1;
    for(auto x : T[u]){
        dfs(x);

        S = mult(S, add(dp[x][0], dp[x][1]));
        S = add(S, mult(W, dp[x][1]));
        W = mult(W, add(dp[x][0], dp[x][1]));
        dp[u][0] = mult(dp[u][0], add(dp[x][0], dp[x][1]));
    }
    dp[u][1] = S;
    dp[u][0] = mult(dp[u][0], (int)T[u].size());
    dp[u][0] = add(dp[u][0], -dp[u][1]);
}

int n, m;

void init(int _n, int _m, std::vector<int> P, std::vector<int> A) {
    n = _n;
    m = _m;
    for(int i = 1; i < n + m; i ++ ){
        T[P[i]].push_back(i);
    }
    for(int i = 0 ; i < m ; i ++ ){
        if(A[i] == 0){
            dp[i + n][0] = 1;
            dp[i + n][1] = 0;
        }
        else{
            dp[i + n][0] = 0;
            dp[i + n][1] = 1;
        }
    }
}

int count_ways(int li, int ri) {
    for(int i = li ; i <= ri ; 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