oj.uz

Submission #631590

# Submission time Handle Problem Language Result Execution time Memory
631590 2022-08-18T09:27:51 Z alontanay Digital Circuit (IOI22_circuit) C++17
2 / 100
 772 ms 9060 KB 
#include <bits/stdc++.h>
#include "circuit.h"

using namespace std;
using ll = long long;

const int mxN = 100005;
const int MOD = 1000002022;

int coef[mxN];
vector<int> state;

struct Seg {
    ll val;
    ll sum = 0;
    bool flip = false;
    int l, r, mid;
    Seg *ls, *rs;
    Seg(int l, int r): l(l), r(r), mid((l+r)/2) {
        if(l + 1 < r) {
            ls = new Seg(l,mid);
            rs = new Seg(mid,r);
            sum = (ls->sum + rs->sum)%MOD;
            val = (ls->val + rs->val)%MOD;
        } else {
            sum = coef[l];
            val = (coef[l]*state[l]);
        }
    }
    void push() {
        if(!flip) { return; }
        if(l + 1 < r) {
            ls->flip ^= true;
            rs->flip ^= true;
        }
        flip = false;
        val = (MOD + sum - val)%MOD;
    }
    void update(int a, int b) {
        push();
        if(a >= r || b <= l) { return; }
        if(a <= l && b >= r) {
            flip ^= true;
            push();
            return;
        }
        ls->update(a,b);
        rs->update(a,b);
        val = (ls->val + rs->val)%MOD;
    }
};

ll sub_mul[mxN];
ll ex_mul[mxN];
ll deg[mxN];
vector<int> cs[mxN];

void get_mul(int node) {
    ll mul = deg[node];
    for(int ne : cs[node]) {
        get_mul(ne);
        mul *= sub_mul[ne];
        mul %= MOD;
    }
    sub_mul[node] = mul;
}

void dfs(int node, ll val = 1) {
    vector<ll> muls;
    ll cur_res = val;
    for(int ne: cs[node]) {
        muls.push_back(sub_mul[ne]);
        cur_res *= sub_mul[ne];
        cur_res %= MOD;
    }
    ex_mul[node] = cur_res;
    int sz = muls.size();
    vector<ll> pre(sz+1);
    vector<ll> suf(sz+1);
    pre[0] = 1;
    suf[sz] = 1;
    for(int i = 1; i <= sz; i ++) {
        pre[i] = pre[i-1] * muls[i-1];
        pre[i] %= MOD;
    }
    for(int i = sz - 1; i >= 0; i --) {
        suf[i] = suf[i+1] * muls[i];
        suf[i] %= MOD;
    }
    int idx = 0;
    for(int ne : cs[node]) {
        ll cur_mul = (pre[idx] * suf[idx+1])%MOD;
        dfs(ne,val*cur_mul);
        idx ++;
    }
}

Seg *seg;
int n;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n = N;
    state = A;
    for(int i = 1; i < N; i ++) {
        cs[P[i]].push_back(i);
    }
    for(int i = 1; i < N + M; i ++) {
      deg[P[i]] ++;
    }
    get_mul(0);
    dfs(0);
    for(int i = 0; i < M; i ++) {
        coef[i] = ex_mul[P[N+i]];
    }
    seg = new Seg(0,M);
}

int count_ways(int L, int R) {
    L -= n;
    R -= n;
    seg->update(L,R+1);
    return seg->val;
}

Subtask #1
2.0 / 2.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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