Submission #680999

#	Time	Username	Problem	Language	Result	Execution time	Memory
680999		Ninja_Kunai	Digital Circuit (IOI22_circuit)	C++17	18 / 100	3026 ms	7432 KiB

circuit

/**
*    Author :  Nguyen Tuan Vu
*    Created : 11.01.2023
**/

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v)  (v).begin(), (v).end()
#define REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + rng() % (r - l + 1);}

const int N = 2e5 + 5;
const int Mod = 1e9 + 2022;
int n, m, Sub3, Sub5;
vector <int> par, a, adj[N];

struct Fenwick_Tree {
    vector <int> bit;
    Fenwick_Tree(int _m = 0){
        m = _m;
        bit.resize(m + 7, 0);
    }

    void update(int u, int v, int val) {
        for(; u <= m; u += u & -u) bit[u] += val;
        for(++v; v <= m; v += v & -v) bit[v] -= val;
    }

    int get(int u) {
        int ans = 0;
        for (; u; u -= u & -u) ans += bit[u];
        return ans;
    }
} mybit;

void add(int &x, int k) {
    x += k;
    if (x >= Mod) x -= Mod;
}

namespace sub3 {
    bool check() {
        if (n <= 1000 && m <= 1000) return true;
        return false;
    }

    int dp[N][2], f[2][N];
    void dfs(int u) {
        dp[u][0] = dp[u][1] = 0;
        if (u >= n) dp[u][a[u - n] ^ (mybit.get(u - n + 1) & 1)] = 1;
        for (auto v : adj[u]) dfs(v);
        int sz = adj[u].size();
        FOR(i, 0, sz) f[0][i] = f[1][i] = 0;
        f[1][0] = 1;
        int sum = 0;
        REP(i, sz) {
            int v = adj[u][i];
            FOR(Left, 0, sum) {
                add(f[i & 1][Left], 1ll *  f[(i + 1) & 1][Left] * dp[v][0] % Mod);
                add(f[i & 1][Left + 1], 1ll * f[(i + 1) & 1][Left] * dp[v][1] % Mod);
                f[(i + 1) & 1][Left] = 0;
            }

            //if (u == 2) cout << f[i & 1][0] << ' ' << f[i & 1][1] << '\n';
            sum++;
        }

        //if (u == 2) cout << f[(sz - 1) & 1][0] << ' ' << f[(sz - 1) & 1][1] << '\n';
        FOR(j, 0, sz) {
            add(dp[u][0], 1ll * f[(sz - 1) & 1][j] * (sz - j) % Mod);
            add(dp[u][1], 1ll * f[(sz - 1) & 1][j] * j % Mod);
        }

        //cout << u << ' ' << dp[u][0] << ' ' << dp[u][1] << '\n';
    }

    int solve(int L, int R) {
        mybit.update(L - n + 1, R - n + 1, 1);
        //FOR(i, 1, m) cout << ((mybit.get(i) & 1) ^ a[i - 1]) << " \n"[i == m];
        dfs(0);
        return dp[0][1];
    }
}

void init(int N, int M, vector <int> P, vector <int> A) {
    n = N; m = M;
    par = P; a = A;
    mybit = Fenwick_Tree(m);
    FOR(i, 1, n + m - 1) {
        adj[P[i]].push_back(i);
    }

    if (sub3::check()) Sub3 = 1;
    //cout << Sub3 << '\n';
}

int count_ways(int l, int r) {
    if (Sub3 == 1) return sub3::solve(l, r);
}

/*
==================================================+
INPUT:
--------------------------------------------------|
3 4
-1 0 1 2 1 1 0
1 0 1 0
3
3 4
4 5
3 6

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
2
0
6
--------------------------------------------------|
==================================================+
*/

Compilation message (stderr)

circuit.cpp: In function 'int count_ways(int, int)':
circuit.cpp:119:1: warning: control reaches end of non-void function [-Wreturn-type]
  119 | }
      | ^

• 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