Submission #1063330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063330		jerzyk	Digital Circuit (IOI22_circuit)	C++17	100 / 100	817 ms	32316 KiB

circuit

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000002022LL;
const int N = 1<<18;
ll drz[2 * N][2];
int laz[2 * N];
vector<int> ed[N];
ll il[N];
int bas;

void Query(int v, int p, int k, int pz, int kz)
{
    if(p > kz || k < pz) return;
    if(p >= pz && k <= kz)
    {
        swap(drz[v][0], drz[v][1]);
        laz[v] ^= 1;
        return;
    }
    Query(v * 2, p, (p + k) / 2, pz, kz);
    Query(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz);
    drz[v][0] = (drz[v * 2][0] + drz[v * 2 + 1][0]) % M;
    drz[v][1] = (drz[v * 2][1] + drz[v * 2 + 1][1]) % M;
    if(laz[v] == 1)
        swap(drz[v][0], drz[v][1]);
}

ll QP(ll a, ll n)
{
    ll ans = 1LL;
    while(n > 0LL)
    {
        if(n % 2LL == 1LL)
            ans = (ans * a) % M;
        a = (a * a) % M;
        n /= 2LL;
    }
    return ans;
}

void DFSL(int v)
{
    il[v] = max(1LL, (ll)ed[v].size());
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        DFSL(ed[v][i]);
        il[v] = (il[v] * il[ed[v][i]]) % M;
    }
}

void DFS(int v, ll cur)
{
    if(v > bas)
    {
        drz[v - bas + N][0] += cur;
        return;
    }
    vector<ll> prf;
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        prf.pb(il[ed[v][i]]);
        if(i > 0)
            prf[i] = (prf[i] * prf[i - 1]) % M;
    }
    for(int i = (int)ed[v].size() - 1; i >= 0; --i)
    {
        ll xd = cur;
        if(i > 0) xd = (xd * prf[i - 1]) % M;
        DFS(ed[v][i], xd);
        cur = (cur * il[ed[v][i]]) % M;
    }
}

void init(int XN, int XM, vector<int> P, vector<int> A)
{
    int n = XN + XM;
    bas = XN;
    for(int i = 1; i < n; ++i)
        ed[P[i] + 1].pb(i + 1);
    DFSL(1);
    DFS(1, 1LL);
    for(int i = 1; i <= n - bas; ++i)
    {
        if(A[i - 1] == 0)
            swap(drz[i + N][0], drz[i + N][1]);
    }

    for(int i = N - 1; i >= 1; --i)
    {
        drz[i][0] = (drz[i * 2][0] + drz[i * 2 + 1][0]) % M;
        drz[i][1] = (drz[i * 2][1] + drz[i * 2 + 1][1]) % M;
    }
}

int count_ways(int L, int R)
{
    ++L; ++R;
    L -= bas; R -= bas;
    Query(1, 0, N - 1, L, R);
    return drz[1][0];
}

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