Submission #1247161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247161		DeathIsAwe	Digital Circuit (IOI22_circuit)	C++20	18 / 100	3098 ms	8668 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define ld long double
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int n, m;
vector<int> p, a;
vector<vector<int>> children;
const int modnum = 1000002022;


pair<ll, ll> calc(int x) {
    int k = children[x].size();
    vector<pair<ll, ll>> nums(k);
    for (int i=0;i<k;i++) {
        if (children[x][i] >= n) {
            nums[i].ff = a[children[x][i] - n];
            nums[i].ss = (a[children[x][i] - n] + 1) % 2;
        } else {
            nums[i] = calc(children[x][i]);
        }
    }


    vector<ll> dum(k + 1);
    vector<vector<ll>> one;
    for (int i=0;i<k+1;i++) one.pb(dum);
    for (int i=0;i<k+1;i++) {
        one[i][0] = 0;
    }
    one[0][0] = 1;
    one[0][1] = nums[0].ss;
    for (int i=2;i<k+1;i++) {
        one[0][i] = (one[0][i - 1] * nums[i - 1].ss) % modnum;
    }
    for (int i=1;i<k+1;i++) {
        for (int j=1;j<k+1;j++) {
            one[i][j] = (one[i][j - 1] * nums[j - 1].ss + one[i - 1][j - 1] * nums[j - 1].ff) % modnum;
        }
    }
    /*
    cout << x << " : " << endl;
    for (int i=0;i<k;i++) {
        cout << nums[i].ff << ' ' << nums[i].ss << endl;
    } cout << endl;
    for (int i=0;i<k+1;i++) {
        for (int j=0;j<k+1;j++) {
            cout << one[i][j] << ' ';
        } cout << endl;
    } cout << endl;
    */


    ll zeronum = 0, onenum = 0;
    for (int i=1;i<k+1;i++) {
        for (int j=i;j<k+1;j++) {
            onenum += one[j][k];
            onenum %= modnum;
        }
        for (int j=0;j<i;j++) {
            zeronum += one[j][k];
            zeronum %= modnum;
        }
    }
    //cout << "FINALS " << onenum << ' ' << zeronum << endl;
    return mp(onenum, zeronum);
}


void init(int N, int M, vector<int> P, vector<int> A) {
    n = N; m = M; p = P; a = A;
    vector<int> dum;
    for (int i=0;i<n+m;i++) {
        children.pb(dum);
    }
    for (int i=1;i<n+m;i++) {
        children[p[i]].pb(i);
    }
    /*
    for (int i=0;i<n+m;i++) {
        cout << i << " children ";
        for (int j: children[i]) {
            cout << j << ' ';
        } cout << endl;
    }
    */
}


int count_ways(int L, int R) {
    int l = L, r = R;
    for (int i=l;i<r+1;i++) {
        a[i - n] = (a[i - n] + 1) % 2;
    }
    return calc(0).ff;
}

• 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