Submission #1212264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212264		mmario99	Digital Circuit (IOI22_circuit)	C++20	Compilation error	0 ms	0 KiB

circuit

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static const ll MOD = 1000002022;

static int gN, gM;
static vector<int> parentArr;
static vector<vector<int>> children;
static vector<ll> Sval;
static vector<ll> Wval;
static vector<ll> upVal;
static vector<ll> coef;
static vector<int> leafState;

struct SegTree
{
    int n;
    struct Node
    {
        ll sum;
        ll totCoef;
        bool flip;
    };
    vector<Node> st;

    SegTree(int _n=0) : n(_n)
    {
        if (n > 0) st.resize(4*n);
    }

    void build(int p, int l, int r)
    {
        if (l == r)
        {
            st[p].totCoef = coef[l] % MOD;
            st[p].sum     = (coef[l] * leafState[l]) % MOD;
            st[p].flip    = false;
            return;
        }
        int m = (l + r) >> 1;
        build(p<<1,   l,   m);
        build(p<<1|1, m+1, r);
        st[p].totCoef = (st[p<<1].totCoef + st[p<<1|1].totCoef) % MOD;
        st[p].sum     = (st[p<<1].sum     + st[p<<1|1].sum)     % MOD;
        st[p].flip    = false;
    }

    inline void applyFlip(int p)
    {
        st[p].sum = (st[p].totCoef - st[p].sum) % MOD;
        if (st[p].sum < 0) st[p].sum += MOD;
        st[p].flip = !st[p].flip;
    }

    inline void push(int p)
    {
        if (!st[p].flip) return;
        applyFlip(p<<1);
        applyFlip(p<<1|1);
        st[p].flip = false;
    }

    void updateRange(int p, int l, int r, int i, int j)
    {
        if (j < l || i > r) return;
        if (l >= i && r <= j)
        {
            applyFlip(p);
            return;
        }
        push(p);
        int m = (l + r) >> 1;
        updateRange(p<<1,   l,   m, i, j);
        updateRange(p<<1|1, m+1, r, i, j);
        st[p].sum = (st[p<<1].sum + st[p<<1|1].sum) % MOD;
    }

    void init_build(int _n)
    {
        n = _n;
        st.resize(4*n);
        build(1, 0, n-1);
    }
    void invertInterval(int L, int R)
    {
        updateRange(1, 0, n-1, L, R);
    }
    ll queryAll() const
    {
        return st[1].sum;
    }
};

static SegTree seg;
int nn;


void init(int N, int M, int P[], int A[])
{
    nn = N;
    gN = N;
    gM = M;

    parentArr.resize(N+M);
    for(int i = 0; i < N+M; i++)
    {
        parentArr[i] = P[i];
    }
    children.assign(N+M, {});
    for(int i = 1; i < N+M; i++)
    {
        int p = parentArr[i];
        children[p].push_back(i);
    }

    leafState.resize(M);
    for(int i = 0; i < M; i++)
    {
        leafState[i] = A[i];
    }

    Sval.assign(N+M, 0LL);
    for(int v = N+M-1; v >= 0; v--)
    {
        if (v >= N)
        {
            Sval[v] = 1;
        }
        else
        {
            ll prod = 1;
            int d = (int)children[v].size();
            for(int c : children[v])
            {
                prod = (prod * Sval[c]) % MOD;
            }
            prod = (prod * d) % MOD;
            Sval[v] = prod;
        }
    }

    Wval.assign(N+M, 1LL);
    for(int v = 0; v < N; v++)
    {
        int d = (int)children[v].size();
        if (d == 0) continue;
        vector<ll> pref(d), suf(d);
        for(int i = 0; i < d; i++)
        {
            pref[i] = Sval[ children[v][i] ];
            suf[i] = pref[i];
        }
        for(int i = 1; i < d; i++)
        {
            pref[i] = (pref[i] * pref[i-1]) % MOD;
        }
        for(int i = d-2; i >= 0; i--)
        {
            suf[i] = (suf[i] * suf[i+1]) % MOD;
        }
        for(int i = 0; i < d; i++)
        {
            ll left  = (i > 0    ? pref[i-1]   : 1LL);
            ll right = (i+1 < d  ? suf[i+1]    : 1LL);
            ll w = (left * right) % MOD;
            int c = children[v][i];
            Wval[c] = w;
        }
    }
    upVal.assign(N+M, 1LL);
    vector<int> queue;
    queue.reserve(N+M);
    queue.push_back(0);
    for(int idx = 0; idx < (int)queue.size(); idx++)
    {
        int v = queue[idx];
        for(int c : children[v])
        {
            upVal[c] = (upVal[v] * Wval[c]) % MOD;
            queue.push_back(c);
        }
    }
    coef.assign(M, 0LL);
    for(int i = 0; i < M; i++)
    {
        coef[i] = upVal[N + i];
    }
    seg = SegTree(M);
    seg.init_build(M);
}
int count_ways(int L, int R)
{
    int l = L - nn;
    int r = R - nn;
    seg.invertInterval(l, r);

    ll ans = seg.queryAll() % MOD;
    return (int)ans;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccOeLeda.o: in function `main':
stub.cpp:(.text.startup+0x140): undefined reference to `init(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status