Submission #628863

#	Time	Username	Problem	Language	Result	Execution time	Memory
628863		welleyth	Digital Circuit (IOI22_circuit)	C++17	11 / 100	3061 ms	12444 KiB

circuit

#include "circuit.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;

constexpr int NN = (int)2e5+111;
constexpr int md = (int)1e9+2022;
typedef long long ll;
int a[NN];
std::vector<int> g[NN];
ll dp[2][NN];
ll all[NN];
int p[NN];
int n,m;

void dfs(int v){
    if(g[v].empty())
        return;
    for(auto& to : g[v]){
        dfs(to);
    }
    int sz = g[v].size();
    for(int i = 1; i < (1 << sz); i++){
        int k = 1;
        for(int j = 0; j < sz; j++){
            k = (k * dp[i >> j & 1][g[v][j]]) % md;
        }
        dp[1][v] += __builtin_popcount(i) * k;
        dp[1][v] %= md;
    }
    all[v] = g[v].size();
    for(auto& to : g[v]){
        all[v] = (all[v] * all[to]) % md;
    }
    dp[0][v] = (all[v] - dp[1][v] + md) % md;
    return;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    p[0] = -1;
    for(int i = 1; i < N+M; i++){
        g[P[i]].push_back(i);
        p[i] = P[i];
    }
    for(int i = 0; i < M; i++){
        a[i+N] = A[i];
        dp[1][i+N] = A[i];
        dp[0][i+N] = A[i] ^ 1;
        all[i+N] = 1;
    }
    n = N;
    m = M;
    dfs(0);
    return;
}

void go(int v){
    if(v == -1)
        return;
//    cerr << "v = " << v << "\n";
    if(g[v].empty()){
        go(p[v]);
        return;
    }
    int sz = g[v].size();
    dp[1][v] = 0;
    dp[0][v] = 0;
    for(int i = 1; i < (1 << sz); i++){
        int k = 1;
        for(int j = 0; j < sz; j++){
            k = (k * dp[i >> j & 1][g[v][j]]) % md;
        }
        dp[1][v] += __builtin_popcount(i) * k % md;
        dp[1][v] %= md;
    }
    all[v] = g[v].size();
    for(auto& to : g[v]){
        all[v] = (all[v] * all[to]) % md;
    }
    dp[0][v] = (all[v] - dp[1][v] + md) % md;
    go(p[v]);
    return;
}

int count_ways(int L, int R) {
    for(int i = L; i <= R; i++){
        a[i] ^= 1;
        dp[1][i] ^= 1;
        dp[0][i] ^= 1;
        go(p[i]);
    }
//    dfs(0);
    return dp[1][0];
}
/**
3 4 3
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
3 6

1 2 1
-1 0 0
0 0
1 1

**/

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