oj.uz

Submission #1067076

# Submission time Handle Problem Language Result Execution time Memory
1067076 2024-08-20T10:41:16 Z j_vdd16 Digital Circuit (IOI22_circuit) C++17
2 / 100
 441 ms 5464 KB 
#include "circuit.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

constexpr int mod = 1'000'002'022;

struct SegTree {
    int n, N;

    vi prefix;
    int prefSum(int l, int r) {
        return (prefix[r] - prefix[l] + mod) % mod;
    }

    vi tree;
    vi lazy;
    SegTree() = default;
    SegTree(vi values, vector<signed> assignment) {
        n = values.size();
        N = 1;
        while (N < n) N *= 2;

        prefix = vi(n + 1);
        loop(i, n) {
            prefix[i + 1] = (prefix[i] + values[i]) % mod;
        }

        tree = vi(2 * N);
        lazy = vi(2 * N);
        loop(i, n) {
            tree[N + i] = assignment[i] ? values[i] : 0;
        }
        for (int i = N - 1; i >= 1; i--) {
            tree[i] = (tree[2 * i] + tree[2 * i + 1]) % mod;
        }
    }

    int get(int l, int r, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1) {
            tr = N;
        }
        
        if (lazy[i]) {
            tree[i] = (prefSum(tl, tr) - tree[i] + mod) % mod;
            if (tr - tl > 1) {
                lazy[2 * i] ^= true;
                lazy[2 * i + 1] ^= true;
            }
            lazy[i] = false;
        }

        if (tr <= l || tl >= r) {
            return tree[i];
        }

        if (tl >= l && tr <= r) {
            tree[i] = (prefSum(tl, tr) - tree[i] + mod) % mod;
            if (tr - tl > 1) {
                lazy[2 * i] ^= true;
                lazy[2 * i + 1] ^= true;
            }

            return tree[i];
        }

        int tm = (tl + tr) / 2;
        tree[i] = (get(l, r, 2 * i, tl, tm) + get(l, r, 2 * i + 1, tm, tr)) % mod;
        return tree[i];
    }
};

int n, m;
vvi children;
vector<signed> assignment;
vi c;

vi factors;
void cDfs(int node) {
    if (node >= n) {
        c[node] = 1;
        return;
    }

    vii out;
    c[node] = children[node].size();
    for (int child : children[node]) {
        cDfs(child);

        c[node] = (c[node] * c[child]) % mod;
    }
}
void factorDfs(int node, int factor) {
    if (node >= n) {
        factors[node - n] = factor;
        return;
    }

    int deg = children[node].size();
    vi factorPref(deg + 1, 1);
    for (int i = deg - 1; i >= 0; i--) {
        factorPref[i] = (c[children[node][i]] * factorPref[i + 1]) % mod;
    }

    int factorSoFar = 1;
    loop(i, deg) {
        factorDfs(children[node][i], (factorSoFar * factorPref[i + 1]) % mod);

        factorSoFar = (factorSoFar * c[children[node][i]]) % mod;
    }

    //factorDfs(children[node][0], (factor * c[children[node][1]]) % mod);
    //factorDfs(children[node][1], (factor * c[children[node][0]]) % mod);
}

SegTree segTree;
void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
    n = N;
    m = M;
    children = vvi(n);
    assignment = A;
    c = vi(n + m);
    factors = vi(m);

    for (int i = 1; i < n + m; i++) {
        children[P[i]].push_back(i);
    }

    cDfs(0);
    factorDfs(0, 1);

    segTree = SegTree(factors, assignment);
}

signed count_ways(signed L, signed R) {
    int res = segTree.get(L - n, R - n + 1);
    
    return res;
    /*
    3 children:
    a = 
        1 * (a[0] * b[1] * b[2] + b[0] * a[1] * b[2] + b[0] * b[1] * a[2]) + 
        2 * (a[0] * a[1] * b[2] + a[0] * b[1] * a[2] + b[0] * a[1] * a[2]) +
        3 * (a[0] * a[1] * a[2])
      =
        1 * (a[0] * (c[1] - a[1]) * (c[2] - a[2]))
        2 * (a[0] * a[1] * (c[2] - a[2]))
        3 * (a[0] * a[1] * a[2])
      =
        (1 + 2 - 3) * (a[0] * a[1] * a[2])
        a[0] * c[1] * c[2]
        2 * (a[0] * a[1] * c[2]) - 2 * (a[0] * a[1] * c[2])
      = 
        a[0] * c[1] * c[2]
    

    
    C = c[0] * c[1] * c[2] * 3
    b = C - a
      = 

    2 children:
    a = 
        1 * (a[0] * b[1] + b[0] * a[1]) +
        2 * (a[0] * a[1])
      =
        1 * (a[0] * (c[1] - a[1]) + (c[0] - a[0]) * a[1]) +
        2 * (a[0] * a[1])
      = a[0] * c[1] + c[0] * a[1]
    
    C = c[0] * c[1] * 2
    b = C - a
      = 
    */

}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '128'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '128'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 441 ms 5464 KB 1st lines differ - on the 1st token, expected: '431985922', found: '16402'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 441 ms 5464 KB 1st lines differ - on the 1st token, expected: '431985922', found: '16402'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '128'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '128'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '128'
11 Halted 0 ms 0 KB -