Submission #1182310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182310		PagodePaiva	Digital Circuit (IOI22_circuit)	C++20	100 / 100	423 ms	33212 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>
#include <vector>
#define ll long long

using namespace std;

const ll mod = 1000002022; 
const int N = 300010;
vector <int> g[N];
ll tot[N], c[N];
int pai[N];
vector <int> start;
int n;

struct Segtree{
    struct Node{
        ll val, soma;
        int lazy;
    } tree[4*N], nulo;
    Node join(Node a, Node b){
        Node res;
        res.val = a.val+b.val;
        res.val %= mod;
        res.soma = a.soma+b.soma;
        res.soma %= mod;
        res.lazy = 0;
        return res;
    }
    void unlazy(int node, int l, int r){
        if(!tree[node].lazy) return;
        tree[node].val = tree[node].soma - tree[node].val;
        tree[node].val %= mod;
        tree[node].val += mod;
        tree[node].val %= mod;
        if(l != r){
            tree[2*node].lazy ^= tree[node].lazy;
            tree[2*node+1].lazy ^= tree[node].lazy;
        }
        tree[node].lazy = 0;
    }
    void build(int node, int l, int r){
        if(node == 1){
            nulo.val = nulo.soma = 0;
            nulo.lazy = 0;
        }
        tree[node].lazy = 0;
        if(l == r){
            tree[node].soma = c[l+n-1];
            tree[node].val = (start[l-1] == 1 ? tree[node].soma : 0);
            return;
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    void update(int node, int l, int r, int tl, int tr){
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return;
        if(l <= tl and tr <= r){
            tree[node].lazy ^= 1;
            unlazy(node, tl, tr);
            return;
        }
        int mid =(tl+tr)/2;
        update(2*node, l, r, tl, mid);
        update(2*node+1, l, r, mid+1, tr);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    Node query(int node, int l, int r, int tl, int tr){
        unlazy(node, tl ,tr);
        if(l > tr or tl > r) return nulo;
        if(l <= tl and tr <= r) return tree[node];
        int mid = (tl+tr)/2;
        return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
    }
} seg;

void dfs(int v, int p){
    if(g[v].size() == 0){
        pai[v] = p;
        tot[v] = 1;
        return;
    }
    pai[v] = p;
    tot[v] = 1;
    for(auto x : g[v]){
        dfs(x, v);
        tot[v] *= tot[x];
        tot[v] %= mod;
    }
    tot[v] *= (ll) g[v].size();
    tot[v] %= mod;
    return;
}

ll pref[N], suf[N];

void dfs2(int v, int p){
    // c[v] = mul(dividir(tot[p], mul(g[p].size(), tot[v])), c[p]);
    pref[0] = 1;
    suf[g[v].size()+1] = 1;
    for(int i = 1;i <= g[v].size();i++){
        int x = g[v][i-1];
        pref[i] = (pref[i-1]*tot[x]) % mod;
    }
    for(int i = g[v].size();i > 0;i--){
        int x = g[v][i-1];
        suf[i] = (suf[i+1]*tot[x]) % mod;
    }
    for(int i = 1;i <= g[v].size();i++){
        int x = g[v][i-1];
        c[x] = (pref[i-1]*suf[i+1])% mod;
        c[x] *= c[v];
        c[x] %= mod;
    }
    for(auto x : g[v]){
        dfs2(x, v);
    }
    return;
}

int m;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    start = A;
    m = M;
    n = N;
    for(int i = 1;i < P.size();i++){
        g[P[i]].push_back(i);
    }
    dfs(0, 0);
    c[0] = 1;
    dfs2(0, 0);
    /*for(int i = 0;i < n+m;i++){
        cout << tot[i] << ' ' << c[i] << '\n';
    }
    cout << '\n';*/
    seg.build(1, 1, M);
}

int count_ways(int l, int r) {
    l -= n-1;
    r -= n-1;
    seg.update(1, l, r, 1, m);
    return seg.query(1, 1, m, 1, m).val;
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11