oj.uz

Submission #1067078

# Submission time Handle Problem Language Result Execution time Memory
1067078 2024-08-20T10:42:38 Z j_vdd16 Digital Circuit (IOI22_circuit) C++17
50 / 100
 3000 ms 23304 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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 3081 ms 344 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 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 1 ms 344 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 3081 ms 344 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 5464 KB Output is correct
2 Correct 535 ms 10576 KB Output is correct
3 Correct 611 ms 10628 KB Output is correct
4 Correct 639 ms 10584 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 5464 KB Output is correct
2 Correct 535 ms 10576 KB Output is correct
3 Correct 611 ms 10628 KB Output is correct
4 Correct 639 ms 10584 KB Output is correct
5 Correct 555 ms 5464 KB Output is correct
6 Correct 721 ms 10584 KB Output is correct
7 Correct 687 ms 10584 KB Output is correct
8 Correct 683 ms 10584 KB Output is correct
9 Correct 360 ms 728 KB Output is correct
10 Correct 652 ms 1048 KB Output is correct
11 Correct 651 ms 1052 KB Output is correct
12 Correct 632 ms 1052 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 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 1 ms 344 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 385 ms 5464 KB Output is correct
14 Correct 535 ms 10576 KB Output is correct
15 Correct 611 ms 10628 KB Output is correct
16 Correct 639 ms 10584 KB Output is correct
17 Correct 555 ms 5464 KB Output is correct
18 Correct 721 ms 10584 KB Output is correct
19 Correct 687 ms 10584 KB Output is correct
20 Correct 683 ms 10584 KB Output is correct
21 Correct 360 ms 728 KB Output is correct
22 Correct 652 ms 1048 KB Output is correct
23 Correct 651 ms 1052 KB Output is correct
24 Correct 632 ms 1052 KB Output is correct
25 Correct 645 ms 16720 KB Output is correct
26 Correct 745 ms 16976 KB Output is correct
27 Correct 725 ms 16976 KB Output is correct
28 Correct 610 ms 16976 KB Output is correct
29 Correct 695 ms 23304 KB Output is correct
30 Correct 686 ms 23120 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 3081 ms 344 KB Time limit exceeded
3 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 Execution timed out 3081 ms 344 KB Time limit exceeded
3 Halted 0 ms 0 KB -