oj.uz

Submission #856083

# Submission time Handle Problem Language Result Execution time Memory
856083 2023-10-02T16:24:54 Z Urvuk3 Digital Circuit (IOI22_circuit) C++17
2 / 100
 380 ms 13872 KB 
#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back

void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}

template<typename T,typename V>
void PRINT(pair<T,V>& x){
    cerr<<"{";
    PRINT(x.fi);
    cerr<<",";
    PRINT(x.se);
    cerr<<"}";
}
template<typename T>
void PRINT(T &x){
    int id=0;
    cerr<<"{";
    for(auto _i:x){
        cerr<<(id++ ? "," : "");
        PRINT(_i);
    }
    cerr<<"}";
}
void _PRINT(){
    cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
    PRINT(h);
    if(sizeof...(t)) cerr<<", ";
    _PRINT(t...);
}

#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)

const int mxN=1e5;
const ll MOD=1000002022;

vector<ll> contribute(mxN,1),sub(mxN,1);
vector<int> lazy(4*mxN),adj[mxN];
int N,M;

struct Node{
    ll tmp,all;
}; vector<Node> seg(4*mxN);

Node Merge(Node& n1,Node& n2){
    Node ret={n1.tmp+n2.tmp,n1.all+n2.all};
    return ret;
}

void Propagate(int node,int l,int r){
    if(lazy[node]){
        seg[node].tmp=seg[node].all-seg[node].tmp;
        if(l<=r){
            lazy[2*node]^=1;
            lazy[2*node+1]^=1;
        }
        lazy[node]=0;
    }
}

void Build(int node,int l,int r,vector<int>& A){
    if(l==r){
        seg[node].tmp=(A[l] ? contribute[l+N] : 0);
        seg[node].all=contribute[l+N];
        return;
    }
    Build(2*node,l,mid,A); Build(2*node+1,mid+1,r,A);
    seg[node]=Merge(seg[2*node],seg[2*node+1]);
}

void Update(int node,int l,int r,int L,int R){
    if(l>r) return;
    Propagate(node,l,r);
    if(L>r || R<l) return;
    if(L<=l && r<=R){
        lazy[node]=1;
        Propagate(node,l,r);
        return;
    }
    Update(2*node,l,mid,L,R); Update(2*node+1,mid+1,r,L,R);
    seg[node]=Merge(seg[2*node],seg[2*node+1]);
}

void Md(ll& x){
    if(x>=MOD) x%=MOD;
    if(x<0) x+=MOD;
}

void DfsSub(int node,int par){
    int c=0;
    for(int v:adj[node]){
        if(v!=par){
            DfsSub(v,node);
            sub[node]*=sub[v]; Md(sub[node]);
            c++;
        }
    }
    if(0<=node && node<N){
        sub[node]*=c; Md(sub[node]);
    }
}

void DfsCon(int node,int par){
    if(par!=-1){
        contribute[node]*=contribute[par];
        Md(contribute[node]);
    }
    vector<ll> pref(sz(adj[node]),1),suf(sz(adj[node]),1);
    for(int i=0;i<sz(adj[node]);i++){
        int v=adj[node][i];
        if(i){
            pref[i]=pref[i-1]; Md(pref[i]);
        }
        if(v!=par){
            pref[i]*=sub[v]; Md(pref[i]);
        }
    }
    for(int i=sz(adj[node])-1;i>=0;i--){
        int v=adj[node][i];
        if(i!=sz(adj[node])-1){
            suf[i]=suf[i+1]; Md(suf[i]);
        }
        if(v!=par){
            suf[i]*=sub[v]; Md(suf[i]);
        }
    }
    for(int i=0;i<sz(adj[node]);i++){
        int v=adj[node][i];
        if(v!=par){
            if(i) contribute[v]*=pref[i-1];
            if(i<sz(adj[node])-1) contribute[v]*=suf[i+1];
        }
    }
    for(int v:adj[node]){
        if(v!=par){
            DfsCon(v,node);
        }
    }
}

void init(int N1, int M1, std::vector<int> P, std::vector<int> A) {
    N=N1,M=M1;
    for(int i=1;i<N+M;i++){
        adj[P[i]].pb(i);
    }
    DfsSub(0,-1);
    DfsCon(0,-1);
    Build(1,0,M-1,A);
}

int count_ways(int L, int R) {
    Update(1,0,M-1,L-N,R-N);
    return seg[1].tmp;
}

Subtask #1
2.0 / 2.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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