oj.uz

Submission #634513

# Submission time Handle Problem Language Result Execution time Memory
634513 2022-08-24T13:52:21 Z mosiashvililuka Digital Circuit (IOI22_circuit) C++17
2 / 100
 715 ms 10868 KB 
#include<bits/stdc++.h>
#include "circuit.h"
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,msh[200009],f[200009],K[800009],mod=1000002022LL,pas,DP[200009],DP2[200009],DP3[200009],jm[800009],seg[800009],seg2[800009],l,r,z,za;
vector <long long> v[200009];
void dfs(long long q, long long w){
    if(v[q].size()==0){
        DP[q]=1;
        return;
    }
    DP[q]=v[q].size();
    for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        dfs((*it),q);
        DP[q]*=DP[(*it)];DP[q]%=mod;
    }
    zx=1;
    for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        DP2[(*it)]=zx;
        zx*=DP[(*it)];zx%=mod;
    }
    vector <long long>::iterator it=v[q].end();it--;
    zx=1;
    while(1){
        DP2[(*it)]*=zx;DP2[(*it)]%=mod;
        zx*=DP[(*it)];zx%=mod;
        if(it==v[q].begin()) break;
        it--;
    }
}
void dfs2(int q, int w){
    DP3[q]*=DP2[q];DP3[q]%=mod;
    for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        DP3[(*it)]=DP3[q];
        dfs2((*it),q);
    }
}
void bld(long long q, long long w, long long rr){
    if(q==w){
        if(f[q]==1){
            seg[rr]=K[q];
        }
        return;
    }
    bld(q,(q+w)/2,rr*2);
    bld((q+w)/2+1,w,rr*2+1);
    seg[rr]=seg[rr*2]+seg[rr*2+1];seg[rr]%=mod;
}
void init(int NN, int MM, std::vector<int> PP, std::vector<int> AA) {
    a=NN+MM;
    for(i=1; i<a; i++){
        msh[i+1]=PP[i]+1;
        v[msh[i+1]].push_back(i+1);
    }
    for(i=NN+1; i<=a; i++){
        f[i]=AA[i-NN-1];
    }
    DP2[1]=1;DP3[1]=1;
    dfs(1,0);
    dfs2(1,0);
    for(i=NN+1; i<=a; i++){
        K[i]=DP3[i];
    }
    za=1;
    while(za<a) za*=2;
    for(i=1; i<=za; i++){
        jm[i]=jm[i-1]+K[i];jm[i]%=mod;
    }
    bld(1,za,1);
}
void pushdown(long long q, long long w, long long rr){
    if(q!=w){
        seg2[rr*2]^=seg2[rr];
        seg2[rr*2+1]^=seg2[rr];
    }
    if(seg2[rr]!=0){
        seg[rr]=(jm[w]-jm[q-1]+mod)-seg[rr]+mod;
        seg[rr]%=mod;
    }
    seg2[rr]=0;
}
void upd(long long q, long long w, long long rr){
    pushdown(q,w,rr);
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        seg2[rr]=z;
        pushdown(q,w,rr);
        return;
    }
    upd(q,(q+w)/2,rr*2);
    upd((q+w)/2+1,w,rr*2+1);
    seg[rr]=seg[rr*2]+seg[rr*2+1];
}
void read(long long q, long long w, long long rr){
    pushdown(q,w,rr);
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        z+=seg[rr];
        return;
    }
    read(q,(q+w)/2,rr*2);
    read((q+w)/2+1,w,rr*2+1);
}
int count_ways(int L, int R) {
    L++;R++;
    l=L;r=R;z=1;
    upd(1,za,1);
    pushdown(1,za,1);
    l=1;r=a;z=0;
    read(1,za,1);
    return z;
}

Subtask #1
2.0 / 2.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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