oj.uz

Submission #777637

# Submission time Handle Problem Language Result Execution time Memory
777637 2023-07-09T11:44:19 Z alexander707070 Digital Circuit (IOI22_circuit) C++17
52 / 100
 908 ms 82932 KB 
#include<bits/stdc++.h>
#define MAXN 800007
using namespace std;

const long long mod=1000002022;

int n,m,maxdep,pw;
long long st[MAXN],total,diff,zeros,ans,a[MAXN];
long long pref[MAXN],pr,sz[MAXN];
vector<int> v[MAXN],prefs[MAXN],suffs[MAXN];

long long power(long long x,int y){
    if(y==0)return 1;
    if(y==1)return x;
    if(y==2)return (x*x)%mod;
    if(y%2==0)return power(power(x,y/2),2);
    return (power(power(x,y/2),2)*x)%mod;
}

void calc(int x){
    if(v[x].size()==0){
        sz[x]=1; return;
    }

    sz[x]=int(v[x].size());
    prefs[x].resize(v[x].size());
    suffs[x].resize(v[x].size());

    for(int i=0;i<v[x].size();i++){
        calc(v[x][i]);
        sz[x]*=sz[v[x][i]]; 
        sz[x]%=mod;

        prefs[x][i]=sz[v[x][i]];
        if(i>0)prefs[x][i]*=prefs[x][i-1];
        prefs[x][i]%=mod;
    }

    for(int i=v[x].size()-1;i>=0;i--){
        suffs[x][i]=sz[v[x][i]];
        if(i<v[x].size()-1)suffs[x][i]*=suffs[x][i+1];
        suffs[x][i]%=mod;
    }
}

void dfs(int x,long long curr){
    if(v[x].size()==0){
        st[x]=curr;
        return;
    }

    long long t;
    for(int i=0;i<v[x].size();i++){
        if(v[x].size()==1){
            t=1;
        }else if(i==0){
            t=suffs[x][i+1];
        }else if(i==v[x].size()-1){
            t=prefs[x][i-1];
        }else{
            t=(prefs[x][i-1]*suffs[x][i+1])%mod;
        }

        dfs(v[x][i],(curr*t)%mod);
    }
}

long long tree[MAXN],lazy[MAXN];

long long sum(int l,int r){
    if(l==0)return pref[r];
    return (pref[r]-pref[l-1]+mod)%mod;
}

void psh(int v,int l,int r){
    if(lazy[v]==0)return;
    int tt=(l+r)/2;

    tree[2*v]=(sum(l,tt)-tree[2*v]+mod)%mod;
    lazy[2*v]^=1; 
    
    tree[2*v+1]=(sum(tt+1,r)-tree[2*v+1]+mod)%mod;
    lazy[2*v+1]^=1;

    lazy[v]=0;
}

void update(int v,int l,int r,int ll,int rr){
    if(ll>rr)return;
    if(l==ll and r==rr){
        tree[v]=(sum(l,r)-tree[v]+mod)%mod;
        lazy[v]^=1;
    }else{
        int tt=(l+r)/2;
        psh(v,l,r);

        update(2*v,l,tt,ll,min(tt,rr));
        update(2*v+1,tt+1,r,max(tt+1,ll),rr);

        tree[v]=(tree[2*v]+tree[2*v+1])%mod;
    }
}

void init(int N, int M,vector<int> P,vector<int> A){
    n=N; m=M;

    for(int i=1;i<N+M;i++){
        v[P[i]].push_back(i);
    }    

    calc(0);
    dfs(0,1);

    for(int i=0;i<m;i++){
        pref[i]=st[i+N];
        if(i>0)pref[i]+=pref[i-1];
        pref[i]%=mod;
    }

    for(int i=0;i<m;i++){
        if(A[i]==1)update(1,0,m-1,i,i);
    }
}

int count_ways(int L, int R){
    L-=n; R-=n;
    update(1,0,m-1,L,R);

    return tree[1];
}

/*
int main(){
    init(3,4, {-1,0,1,1,2,2,0}, {0,0,0,0});
    cout<<count_ways(3,6)<<"\n";
}
*/

Compilation message

circuit.cpp: In function 'void calc(int)':
circuit.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
circuit.cpp:41:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         if(i<v[x].size()-1)suffs[x][i]*=suffs[x][i+1];
      |            ~^~~~~~~~~~~~~~
circuit.cpp: In function 'void dfs(int, long long int)':
circuit.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
circuit.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         }else if(i==v[x].size()-1){
      |                  ~^~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56656 KB Output is correct
2 Correct 24 ms 56656 KB Output is correct
3 Correct 24 ms 56656 KB Output is correct
4 Correct 24 ms 56636 KB Output is correct
5 Correct 24 ms 56720 KB Output is correct
6 Correct 24 ms 56660 KB Output is correct
7 Correct 25 ms 56736 KB Output is correct
8 Correct 24 ms 56664 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56568 KB Output is correct
2 Correct 25 ms 56732 KB Output is correct
3 Correct 25 ms 56728 KB Output is correct
4 Correct 25 ms 56668 KB Output is correct
5 Correct 24 ms 56660 KB Output is correct
6 Correct 25 ms 56732 KB Output is correct
7 Correct 25 ms 56784 KB Output is correct
8 Correct 25 ms 56744 KB Output is correct
9 Correct 25 ms 56836 KB Output is correct
10 Correct 25 ms 56912 KB Output is correct
11 Correct 25 ms 56860 KB Output is correct
12 Correct 25 ms 56784 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56656 KB Output is correct
2 Correct 24 ms 56656 KB Output is correct
3 Correct 24 ms 56656 KB Output is correct
4 Correct 24 ms 56636 KB Output is correct
5 Correct 24 ms 56720 KB Output is correct
6 Correct 24 ms 56660 KB Output is correct
7 Correct 25 ms 56736 KB Output is correct
8 Correct 24 ms 56664 KB Output is correct
9 Correct 26 ms 56568 KB Output is correct
10 Correct 25 ms 56732 KB Output is correct
11 Correct 25 ms 56728 KB Output is correct
12 Correct 25 ms 56668 KB Output is correct
13 Correct 24 ms 56660 KB Output is correct
14 Correct 25 ms 56732 KB Output is correct
15 Correct 25 ms 56784 KB Output is correct
16 Correct 25 ms 56744 KB Output is correct
17 Correct 25 ms 56836 KB Output is correct
18 Correct 25 ms 56912 KB Output is correct
19 Correct 25 ms 56860 KB Output is correct
20 Correct 25 ms 56784 KB Output is correct
21 Incorrect 24 ms 56784 KB 1st lines differ - on the 1st token, expected: '759476520', found: '863366828'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 62284 KB Output is correct
2 Correct 768 ms 67940 KB Output is correct
3 Correct 734 ms 67912 KB Output is correct
4 Correct 804 ms 67224 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 62284 KB Output is correct
2 Correct 768 ms 67940 KB Output is correct
3 Correct 734 ms 67912 KB Output is correct
4 Correct 804 ms 67224 KB Output is correct
5 Correct 560 ms 62244 KB Output is correct
6 Correct 800 ms 67928 KB Output is correct
7 Correct 831 ms 67948 KB Output is correct
8 Correct 886 ms 67912 KB Output is correct
9 Correct 391 ms 57040 KB Output is correct
10 Correct 815 ms 57424 KB Output is correct
11 Correct 861 ms 57424 KB Output is correct
12 Correct 675 ms 57296 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56568 KB Output is correct
2 Correct 25 ms 56732 KB Output is correct
3 Correct 25 ms 56728 KB Output is correct
4 Correct 25 ms 56668 KB Output is correct
5 Correct 24 ms 56660 KB Output is correct
6 Correct 25 ms 56732 KB Output is correct
7 Correct 25 ms 56784 KB Output is correct
8 Correct 25 ms 56744 KB Output is correct
9 Correct 25 ms 56836 KB Output is correct
10 Correct 25 ms 56912 KB Output is correct
11 Correct 25 ms 56860 KB Output is correct
12 Correct 25 ms 56784 KB Output is correct
13 Correct 632 ms 62284 KB Output is correct
14 Correct 768 ms 67940 KB Output is correct
15 Correct 734 ms 67912 KB Output is correct
16 Correct 804 ms 67224 KB Output is correct
17 Correct 560 ms 62244 KB Output is correct
18 Correct 800 ms 67928 KB Output is correct
19 Correct 831 ms 67948 KB Output is correct
20 Correct 886 ms 67912 KB Output is correct
21 Correct 391 ms 57040 KB Output is correct
22 Correct 815 ms 57424 KB Output is correct
23 Correct 861 ms 57424 KB Output is correct
24 Correct 675 ms 57296 KB Output is correct
25 Correct 763 ms 74920 KB Output is correct
26 Correct 908 ms 75156 KB Output is correct
27 Correct 784 ms 75080 KB Output is correct
28 Correct 849 ms 75056 KB Output is correct
29 Correct 758 ms 82904 KB Output is correct
30 Correct 729 ms 82932 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56656 KB Output is correct
2 Correct 24 ms 56656 KB Output is correct
3 Correct 24 ms 56656 KB Output is correct
4 Correct 24 ms 56636 KB Output is correct
5 Correct 24 ms 56720 KB Output is correct
6 Correct 24 ms 56660 KB Output is correct
7 Correct 25 ms 56736 KB Output is correct
8 Correct 24 ms 56664 KB Output is correct
9 Correct 26 ms 56568 KB Output is correct
10 Correct 25 ms 56732 KB Output is correct
11 Correct 25 ms 56728 KB Output is correct
12 Correct 25 ms 56668 KB Output is correct
13 Correct 24 ms 56660 KB Output is correct
14 Correct 25 ms 56732 KB Output is correct
15 Correct 25 ms 56784 KB Output is correct
16 Correct 25 ms 56744 KB Output is correct
17 Correct 25 ms 56836 KB Output is correct
18 Correct 25 ms 56912 KB Output is correct
19 Correct 25 ms 56860 KB Output is correct
20 Correct 25 ms 56784 KB Output is correct
21 Incorrect 24 ms 56784 KB 1st lines differ - on the 1st token, expected: '759476520', found: '863366828'
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56656 KB Output is correct
2 Correct 24 ms 56656 KB Output is correct
3 Correct 24 ms 56656 KB Output is correct
4 Correct 24 ms 56636 KB Output is correct
5 Correct 24 ms 56720 KB Output is correct
6 Correct 24 ms 56660 KB Output is correct
7 Correct 25 ms 56736 KB Output is correct
8 Correct 24 ms 56664 KB Output is correct
9 Correct 26 ms 56568 KB Output is correct
10 Correct 25 ms 56732 KB Output is correct
11 Correct 25 ms 56728 KB Output is correct
12 Correct 25 ms 56668 KB Output is correct
13 Correct 24 ms 56660 KB Output is correct
14 Correct 25 ms 56732 KB Output is correct
15 Correct 25 ms 56784 KB Output is correct
16 Correct 25 ms 56744 KB Output is correct
17 Correct 25 ms 56836 KB Output is correct
18 Correct 25 ms 56912 KB Output is correct
19 Correct 25 ms 56860 KB Output is correct
20 Correct 25 ms 56784 KB Output is correct
21 Incorrect 24 ms 56784 KB 1st lines differ - on the 1st token, expected: '759476520', found: '863366828'
22 Halted 0 ms 0 KB -