Submission #1069309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069309		mariaclara	Digital Circuit (IOI22_circuit)	C++17	46 / 100	3051 ms	3416 KiB

circuit

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MOD = 1e9 + 2022;
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int n, m;
vector<int> val, tot, a;
vector<vector<int>> filhos;

ll calc_tot(int x) {
    if(x >= n) return 1;

    tot[x] = sz(filhos[x]);
    for(int viz : filhos[x]) {
        tot[x] = (tot[x] * calc_tot(viz))%MOD;
    }

    return tot[x];
}

void dfs(int x) {
    ll at = 1;

    if(x >= n) return;
    
    for(auto viz : filhos[x]) {
        val[viz] = (val[x] * at)%MOD;
        if(viz < n) at = (at*tot[viz])%MOD;
    }

    reverse(all(filhos[x]));
    at = 1;

    for(auto viz : filhos[x]) {
        val[viz] = (val[viz] * at)%MOD;
        if(viz < n) at = (at*tot[viz])%MOD;
    }

    for(auto viz : filhos[x]) dfs(viz);
}

void init(int N, int M, vector<int> P, vector<int> A) {
    val.resize(N+M);
    tot.resize(N);
    filhos.resize(N);
    a = A;
    n = N;
    m = M;

    for(int i = 1; i < N+M; i++)
        filhos[P[i]].pb(i);

    calc_tot(0);
    val[0] = 1;
    dfs(0);
}

int count_ways(int L, int R) {
    for(int i = L; i <= R; i++) a[i-n] = 1-a[i-n];

    ll ans = 0;
    for(int i = n; i < n + m; i++)
        if(a[i-n]) ans = (ans + val[i])%MOD;

    return ans;
}

• 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: 28 / 28
• Subtask 8: 0 / 11