oj.uz

Submission #799530

# Submission time Handle Problem Language Result Execution time Memory
799530 2023-07-31T15:39:11 Z JakobZorz Digital Circuit (IOI22_circuit) C++17
100 / 100
 1075 ms 41472 KB 
#include"circuit.h"
#include<vector>
#include<iostream>
using namespace std;
typedef long long ll;

const int MOD=1000002022;
const int TREE_SIZE=1<<18;

int parents[200000];
ll sub_mul[200000];
vector<int>children[200000];
int n,m;
ll vals[100000];

struct SegTree{
    vector<int>tree;
    vector<int>tree_val;
    vector<bool>lazy;
    
    void init_tree(int node,int l,int r){
        int m=(l+r)/2;
        if(m==l)
            return;
        
        init_tree(2*node,l,m);
        init_tree(2*node+1,m,r);
        tree[node]=tree[2*node]+tree[2*node+1];
        tree[node]%=MOD;
    }
    
    SegTree(ll*arr,int size){
        tree.resize(2*TREE_SIZE);
        tree_val.resize(2*TREE_SIZE);
        lazy.resize(2*TREE_SIZE);
        for(int i=0;i<size;i++)
            tree[TREE_SIZE+i]=arr[i];
        init_tree(1,0,TREE_SIZE);
    }
    
    int get(){
        return tree_val[1];
    }
    
    void push(int node,int l,int r){
        if(lazy[node]){
            lazy[node]=false;
            tree_val[node]=tree[node]+MOD-tree_val[node];
            tree_val[node]%=MOD;
            if(l<r-1){
                lazy[2*node]=!lazy[2*node];
                lazy[2*node+1]=!lazy[2*node+1];
            }
        }
    }
    
    void toggle(int node,int rl,int rr,int l,int r){
        push(node,l,r);
        
        if(rr<=l||r<=rl)
            return;
        
        if(rl<=l&&r<=rr){
            lazy[node]=true;
            push(node,l,r);
            return;
        }
        
        int m=(l+r)/2;
        toggle(2*node,rl,rr,l,m);
        toggle(2*node+1,rl,rr,m,r);
        
        tree_val[node]=tree_val[2*node]+tree_val[2*node+1];
        tree_val[node]%=MOD;
    }
};

SegTree*segtree;

void dfs2(int node){
    if(children[node].empty()){
        sub_mul[node]=1;
        return;
    }
    
    sub_mul[node]=children[node].size();
    for(int ch:children[node]){
        dfs2(ch);
        sub_mul[node]*=sub_mul[ch];
        sub_mul[node]%=MOD;
    }
}

vector<ll>transform(vector<ll>arr){
    if(arr.size()==1)
        return {1};
    int n=(int)arr.size();
    
    vector<ll>arr1,arr2;
    ll arr1_mul=1,arr2_mul=1;
    for(int i=0;i<n/2;i++){
        arr1.push_back(arr[i]);
        arr1_mul*=arr[i];
        arr1_mul%=MOD;
    }
    for(int i=n/2;i<n;i++){
        arr2.push_back(arr[i]);
        arr2_mul*=arr[i];
        arr2_mul%=MOD;
    }
    
    vector<ll>res1=transform(arr1),res2=transform(arr2);
    
    vector<ll>res;
    for(ll i:res1)
        res.push_back((i*arr2_mul)%MOD);
    for(ll i:res2)
        res.push_back((i*arr1_mul)%MOD);
    
    return res;
}

void dfs3(int node,ll val){
    if(children[node].empty()){
        vals[node-n]=val;
        return;
    }
    
    vector<ll>arr(children[node].size());
    for(int i=0;i<(int)children[node].size();i++)
        arr[i]=sub_mul[children[node][i]];
    vector<ll>res=transform(arr);
    
    for(int i=0;i<(int)children[node].size();i++){
        ll val2=val*res[i];
        val2%=MOD;
        dfs3(children[node][i],val2);
    }
    
    /*for(int ch:children[node]){
        ll val2=val;
        for(int ch2:children[node]){
            if(ch2!=ch){
                val2*=sub_mul[ch2];
                val2%=MOD;
            }
        }
        dfs3(ch,val2);
    }*/
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n=N;
    m=M;
    for(int i=0;i<n+m;i++){
        parents[i]=P[i];
        if(parents[i]!=-1)
            children[parents[i]].push_back(i);
    }
    
    dfs2(0);
    dfs3(0,1);
    
    segtree=new SegTree(vals,m);
    
    for(int i=0;i<(int)A.size();i++)
        if(A[i]==1)
            segtree->toggle(1,i,i+1,0,TREE_SIZE);
}

int count_ways(int L, int R) {
    L-=n;
    R-=n;
    segtree->toggle(1,L,R+1,0,TREE_SIZE);
    
    /*for(int i=0;i<m;i++)
        cout<<active[i]<<" ";
    cout<<"\n";
    for(int i=0;i<m;i++)
        cout<<vals[i]<<" ";
    cout<<"\n";*/
    
    
    return segtree->get();
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9168 KB Output is correct
2 Correct 5 ms 9164 KB Output is correct
3 Correct 7 ms 9216 KB Output is correct
4 Correct 5 ms 9168 KB Output is correct
5 Correct 8 ms 9292 KB Output is correct
6 Correct 5 ms 9172 KB Output is correct
7 Correct 5 ms 9168 KB Output is correct
8 Correct 7 ms 9168 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9168 KB Output is correct
2 Correct 6 ms 9168 KB Output is correct
3 Correct 6 ms 9136 KB Output is correct
4 Correct 7 ms 9168 KB Output is correct
5 Correct 5 ms 9168 KB Output is correct
6 Correct 5 ms 9168 KB Output is correct
7 Correct 6 ms 9168 KB Output is correct
8 Correct 5 ms 9240 KB Output is correct
9 Correct 6 ms 9168 KB Output is correct
10 Correct 6 ms 9432 KB Output is correct
11 Correct 6 ms 9424 KB Output is correct
12 Correct 6 ms 9172 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9168 KB Output is correct
2 Correct 5 ms 9164 KB Output is correct
3 Correct 7 ms 9216 KB Output is correct
4 Correct 5 ms 9168 KB Output is correct
5 Correct 8 ms 9292 KB Output is correct
6 Correct 5 ms 9172 KB Output is correct
7 Correct 5 ms 9168 KB Output is correct
8 Correct 7 ms 9168 KB Output is correct
9 Correct 5 ms 9168 KB Output is correct
10 Correct 6 ms 9168 KB Output is correct
11 Correct 6 ms 9136 KB Output is correct
12 Correct 7 ms 9168 KB Output is correct
13 Correct 5 ms 9168 KB Output is correct
14 Correct 5 ms 9168 KB Output is correct
15 Correct 6 ms 9168 KB Output is correct
16 Correct 5 ms 9240 KB Output is correct
17 Correct 6 ms 9168 KB Output is correct
18 Correct 6 ms 9432 KB Output is correct
19 Correct 6 ms 9424 KB Output is correct
20 Correct 6 ms 9172 KB Output is correct
21 Correct 5 ms 9168 KB Output is correct
22 Correct 5 ms 9168 KB Output is correct
23 Correct 5 ms 9168 KB Output is correct
24 Correct 6 ms 9192 KB Output is correct
25 Correct 6 ms 9168 KB Output is correct
26 Correct 7 ms 9168 KB Output is correct
27 Correct 6 ms 9168 KB Output is correct
28 Correct 6 ms 9316 KB Output is correct
29 Correct 5 ms 9168 KB Output is correct
30 Correct 5 ms 9168 KB Output is correct
31 Correct 5 ms 9424 KB Output is correct
32 Correct 5 ms 9284 KB Output is correct
33 Correct 5 ms 9252 KB Output is correct
34 Correct 5 ms 9168 KB Output is correct
35 Correct 5 ms 9168 KB Output is correct
36 Correct 7 ms 9424 KB Output is correct
37 Correct 6 ms 9552 KB Output is correct
38 Correct 5 ms 9552 KB Output is correct
39 Correct 5 ms 9168 KB Output is correct
40 Correct 6 ms 9216 KB Output is correct
41 Correct 8 ms 9156 KB Output is correct
42 Correct 7 ms 9204 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 11928 KB Output is correct
2 Correct 819 ms 14752 KB Output is correct
3 Correct 746 ms 14724 KB Output is correct
4 Correct 758 ms 14744 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 11928 KB Output is correct
2 Correct 819 ms 14752 KB Output is correct
3 Correct 746 ms 14724 KB Output is correct
4 Correct 758 ms 14744 KB Output is correct
5 Correct 667 ms 11932 KB Output is correct
6 Correct 959 ms 14748 KB Output is correct
7 Correct 889 ms 14728 KB Output is correct
8 Correct 569 ms 14720 KB Output is correct
9 Correct 330 ms 9364 KB Output is correct
10 Correct 737 ms 9424 KB Output is correct
11 Correct 754 ms 9424 KB Output is correct
12 Correct 742 ms 9468 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9168 KB Output is correct
2 Correct 6 ms 9168 KB Output is correct
3 Correct 6 ms 9136 KB Output is correct
4 Correct 7 ms 9168 KB Output is correct
5 Correct 5 ms 9168 KB Output is correct
6 Correct 5 ms 9168 KB Output is correct
7 Correct 6 ms 9168 KB Output is correct
8 Correct 5 ms 9240 KB Output is correct
9 Correct 6 ms 9168 KB Output is correct
10 Correct 6 ms 9432 KB Output is correct
11 Correct 6 ms 9424 KB Output is correct
12 Correct 6 ms 9172 KB Output is correct
13 Correct 486 ms 11928 KB Output is correct
14 Correct 819 ms 14752 KB Output is correct
15 Correct 746 ms 14724 KB Output is correct
16 Correct 758 ms 14744 KB Output is correct
17 Correct 667 ms 11932 KB Output is correct
18 Correct 959 ms 14748 KB Output is correct
19 Correct 889 ms 14728 KB Output is correct
20 Correct 569 ms 14720 KB Output is correct
21 Correct 330 ms 9364 KB Output is correct
22 Correct 737 ms 9424 KB Output is correct
23 Correct 754 ms 9424 KB Output is correct
24 Correct 742 ms 9468 KB Output is correct
25 Correct 1022 ms 17540 KB Output is correct
26 Correct 910 ms 17784 KB Output is correct
27 Correct 989 ms 17696 KB Output is correct
28 Correct 666 ms 17676 KB Output is correct
29 Correct 802 ms 35420 KB Output is correct
30 Correct 761 ms 35516 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9168 KB Output is correct
2 Correct 5 ms 9164 KB Output is correct
3 Correct 7 ms 9216 KB Output is correct
4 Correct 5 ms 9168 KB Output is correct
5 Correct 8 ms 9292 KB Output is correct
6 Correct 5 ms 9172 KB Output is correct
7 Correct 5 ms 9168 KB Output is correct
8 Correct 7 ms 9168 KB Output is correct
9 Correct 5 ms 9168 KB Output is correct
10 Correct 6 ms 9168 KB Output is correct
11 Correct 6 ms 9136 KB Output is correct
12 Correct 7 ms 9168 KB Output is correct
13 Correct 5 ms 9168 KB Output is correct
14 Correct 5 ms 9168 KB Output is correct
15 Correct 6 ms 9168 KB Output is correct
16 Correct 5 ms 9240 KB Output is correct
17 Correct 6 ms 9168 KB Output is correct
18 Correct 6 ms 9432 KB Output is correct
19 Correct 6 ms 9424 KB Output is correct
20 Correct 6 ms 9172 KB Output is correct
21 Correct 5 ms 9168 KB Output is correct
22 Correct 5 ms 9168 KB Output is correct
23 Correct 5 ms 9168 KB Output is correct
24 Correct 6 ms 9192 KB Output is correct
25 Correct 6 ms 9168 KB Output is correct
26 Correct 7 ms 9168 KB Output is correct
27 Correct 6 ms 9168 KB Output is correct
28 Correct 6 ms 9316 KB Output is correct
29 Correct 5 ms 9168 KB Output is correct
30 Correct 5 ms 9168 KB Output is correct
31 Correct 5 ms 9424 KB Output is correct
32 Correct 5 ms 9284 KB Output is correct
33 Correct 5 ms 9252 KB Output is correct
34 Correct 5 ms 9168 KB Output is correct
35 Correct 5 ms 9168 KB Output is correct
36 Correct 7 ms 9424 KB Output is correct
37 Correct 6 ms 9552 KB Output is correct
38 Correct 5 ms 9552 KB Output is correct
39 Correct 5 ms 9168 KB Output is correct
40 Correct 6 ms 9216 KB Output is correct
41 Correct 8 ms 9156 KB Output is correct
42 Correct 7 ms 9204 KB Output is correct
43 Correct 624 ms 9424 KB Output is correct
44 Correct 807 ms 9424 KB Output is correct
45 Correct 876 ms 9424 KB Output is correct
46 Correct 704 ms 9552 KB Output is correct
47 Correct 810 ms 9636 KB Output is correct
48 Correct 891 ms 9552 KB Output is correct
49 Correct 773 ms 9636 KB Output is correct
50 Correct 665 ms 9556 KB Output is correct
51 Correct 768 ms 9640 KB Output is correct
52 Correct 736 ms 9640 KB Output is correct
53 Correct 736 ms 10448 KB Output is correct
54 Correct 655 ms 9536 KB Output is correct
55 Correct 565 ms 9416 KB Output is correct
56 Correct 840 ms 9424 KB Output is correct
57 Correct 685 ms 9296 KB Output is correct
58 Correct 896 ms 10548 KB Output is correct
59 Correct 762 ms 10920 KB Output is correct
60 Correct 781 ms 10920 KB Output is correct
61 Correct 632 ms 9680 KB Output is correct
62 Correct 769 ms 9424 KB Output is correct
63 Correct 799 ms 9296 KB Output is correct
64 Correct 729 ms 9456 KB Output is correct
65 Correct 404 ms 9296 KB Output is correct
66 Correct 704 ms 9572 KB Output is correct
67 Correct 614 ms 9552 KB Output is correct
68 Correct 730 ms 9600 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9168 KB Output is correct
2 Correct 5 ms 9164 KB Output is correct
3 Correct 7 ms 9216 KB Output is correct
4 Correct 5 ms 9168 KB Output is correct
5 Correct 8 ms 9292 KB Output is correct
6 Correct 5 ms 9172 KB Output is correct
7 Correct 5 ms 9168 KB Output is correct
8 Correct 7 ms 9168 KB Output is correct
9 Correct 5 ms 9168 KB Output is correct
10 Correct 6 ms 9168 KB Output is correct
11 Correct 6 ms 9136 KB Output is correct
12 Correct 7 ms 9168 KB Output is correct
13 Correct 5 ms 9168 KB Output is correct
14 Correct 5 ms 9168 KB Output is correct
15 Correct 6 ms 9168 KB Output is correct
16 Correct 5 ms 9240 KB Output is correct
17 Correct 6 ms 9168 KB Output is correct
18 Correct 6 ms 9432 KB Output is correct
19 Correct 6 ms 9424 KB Output is correct
20 Correct 6 ms 9172 KB Output is correct
21 Correct 5 ms 9168 KB Output is correct
22 Correct 5 ms 9168 KB Output is correct
23 Correct 5 ms 9168 KB Output is correct
24 Correct 6 ms 9192 KB Output is correct
25 Correct 6 ms 9168 KB Output is correct
26 Correct 7 ms 9168 KB Output is correct
27 Correct 6 ms 9168 KB Output is correct
28 Correct 6 ms 9316 KB Output is correct
29 Correct 5 ms 9168 KB Output is correct
30 Correct 5 ms 9168 KB Output is correct
31 Correct 5 ms 9424 KB Output is correct
32 Correct 5 ms 9284 KB Output is correct
33 Correct 5 ms 9252 KB Output is correct
34 Correct 5 ms 9168 KB Output is correct
35 Correct 5 ms 9168 KB Output is correct
36 Correct 7 ms 9424 KB Output is correct
37 Correct 6 ms 9552 KB Output is correct
38 Correct 5 ms 9552 KB Output is correct
39 Correct 5 ms 9168 KB Output is correct
40 Correct 6 ms 9216 KB Output is correct
41 Correct 8 ms 9156 KB Output is correct
42 Correct 7 ms 9204 KB Output is correct
43 Correct 486 ms 11928 KB Output is correct
44 Correct 819 ms 14752 KB Output is correct
45 Correct 746 ms 14724 KB Output is correct
46 Correct 758 ms 14744 KB Output is correct
47 Correct 667 ms 11932 KB Output is correct
48 Correct 959 ms 14748 KB Output is correct
49 Correct 889 ms 14728 KB Output is correct
50 Correct 569 ms 14720 KB Output is correct
51 Correct 330 ms 9364 KB Output is correct
52 Correct 737 ms 9424 KB Output is correct
53 Correct 754 ms 9424 KB Output is correct
54 Correct 742 ms 9468 KB Output is correct
55 Correct 1022 ms 17540 KB Output is correct
56 Correct 910 ms 17784 KB Output is correct
57 Correct 989 ms 17696 KB Output is correct
58 Correct 666 ms 17676 KB Output is correct
59 Correct 802 ms 35420 KB Output is correct
60 Correct 761 ms 35516 KB Output is correct
61 Correct 624 ms 9424 KB Output is correct
62 Correct 807 ms 9424 KB Output is correct
63 Correct 876 ms 9424 KB Output is correct
64 Correct 704 ms 9552 KB Output is correct
65 Correct 810 ms 9636 KB Output is correct
66 Correct 891 ms 9552 KB Output is correct
67 Correct 773 ms 9636 KB Output is correct
68 Correct 665 ms 9556 KB Output is correct
69 Correct 768 ms 9640 KB Output is correct
70 Correct 736 ms 9640 KB Output is correct
71 Correct 736 ms 10448 KB Output is correct
72 Correct 655 ms 9536 KB Output is correct
73 Correct 565 ms 9416 KB Output is correct
74 Correct 840 ms 9424 KB Output is correct
75 Correct 685 ms 9296 KB Output is correct
76 Correct 896 ms 10548 KB Output is correct
77 Correct 762 ms 10920 KB Output is correct
78 Correct 781 ms 10920 KB Output is correct
79 Correct 632 ms 9680 KB Output is correct
80 Correct 769 ms 9424 KB Output is correct
81 Correct 799 ms 9296 KB Output is correct
82 Correct 729 ms 9456 KB Output is correct
83 Correct 404 ms 9296 KB Output is correct
84 Correct 704 ms 9572 KB Output is correct
85 Correct 614 ms 9552 KB Output is correct
86 Correct 730 ms 9600 KB Output is correct
87 Correct 6 ms 9168 KB Output is correct
88 Correct 501 ms 16904 KB Output is correct
89 Correct 766 ms 14876 KB Output is correct
90 Correct 849 ms 14596 KB Output is correct
91 Correct 890 ms 17800 KB Output is correct
92 Correct 830 ms 17864 KB Output is correct
93 Correct 811 ms 17796 KB Output is correct
94 Correct 874 ms 17780 KB Output is correct
95 Correct 676 ms 17808 KB Output is correct
96 Correct 834 ms 14996 KB Output is correct
97 Correct 722 ms 15008 KB Output is correct
98 Correct 790 ms 31944 KB Output is correct
99 Correct 997 ms 17664 KB Output is correct
100 Correct 881 ms 15144 KB Output is correct
101 Correct 818 ms 14432 KB Output is correct
102 Correct 1075 ms 13096 KB Output is correct
103 Correct 969 ms 35536 KB Output is correct
104 Correct 817 ms 41472 KB Output is correct
105 Correct 830 ms 41452 KB Output is correct
106 Correct 862 ms 19304 KB Output is correct
107 Correct 929 ms 13564 KB Output is correct
108 Correct 883 ms 13568 KB Output is correct
109 Correct 866 ms 13364 KB Output is correct