Submission #1244164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244164		Hamed_Ghaffari	Digital Circuit (IOI22_circuit)	C++20	100 / 100	398 ms	42096 KiB

circuit

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

using ll = long long;
using pll = pair<ll, ll>;

#define X first
#define Y second
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN=2e5+5, MOD = 1000002022;

int n, m;
ll dp[MXN];
vector<int> g[MXN];

void dfs1(int v) {
    if(v>=n) {
        dp[v] = 1;
        return;
    }
    dp[v] = g[v].size();
    for(int u : g[v]) {
        dfs1(u);
        dp[v] = dp[v]*dp[u]%MOD;
    }
}

pll seg[MXN<<2];
bool lz[MXN<<2];

inline ll md(ll x) { return x - (x>=MOD ? MOD : 0); }
pll operator+(pll x, pll y) { return {md(x.X+y.X), md(x.Y+y.Y)}; }

void modify(int p, pll x, int l=0, int r=m, int id=1) {
    if(r-l == 1) {
        seg[id] = x;
        return;
    }
    p<mid ? modify(p, x, l, mid, lc) : modify(p, x, mid, r, rc);
    seg[id] = seg[lc] + seg[rc];
}
inline void apply(int id) {
    swap(seg[id].X, seg[id].Y);
    lz[id] ^= 1;
}
inline void push(int id) {
    if(lz[id]) {
        apply(lc);
        apply(rc);
        lz[id] = 0;
    }
}
void upd(int s, int e, int l=0, int r=m, int id=1) {
    if(s>=r || l>=e) return;
    if(s<=l && r<=e) {
        apply(id);
        return;
    }
    push(id);
    upd(s, e, l, mid, lc);
    upd(s, e, mid, r, rc);
    seg[id] = seg[lc] + seg[rc];
}

vector<int> A;

void dfs2(int v, ll cur=1) {
    if(v>=n) return modify(v-n, A[v-n] ? pll(cur, 0) : pll(0, cur));
    vector<ll> pre(g[v].size()), suf(g[v].size());
    pre[0] = 1;
    for(int i=1; i<g[v].size(); i++)
        pre[i] = pre[i-1]*dp[g[v][i-1]]%MOD;
    suf[(int)g[v].size()-1] = 1;
    for(int i=(int)g[v].size()-2; i>=0; i--)
        suf[i] = suf[i+1]*dp[g[v][i+1]]%MOD;
    for(int i=0; i<g[v].size(); i++)
        dfs2(g[v][i], cur*pre[i]%MOD*suf[i]%MOD);
}

void init(int N, int M, vector<int> P, vector<int> A) {
    n = N;
    m = M;
    ::A = A;
    for(int i=1; i<N+M; i++)
        g[P[i]].push_back(i);
    dfs1(0);
    dfs2(0);
}

int count_ways(int L, int R) {
    upd(L-n, R-n+1);
    return seg[1].X;
}

• 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