oj.uz

Submission #1058399

# Submission time Handle Problem Language Result Execution time Memory
1058399 2024-08-14T09:47:45 Z Huseyn123 Digital Circuit (IOI22_circuit) C++17
52 / 100
 749 ms 33872 KB 
#include <bits/stdc++.h> 
#include "circuit.h"
#define MAX 200001
using namespace std; 
typedef long long ll;
int n,m; 
const int mod=1000002022;
vector<vector<int>> g;
long long dp[MAX],dp1[MAX];
void dfs(int v){
  if(v>=n){
    dp[v]=1; 
    return;
  }
  dp[v]=(int)g[v].size();
  for(auto x:g[v]){
    dfs(x);
    dp[v]*=dp[x];
    dp[v]%=mod;
  }
}
void dfs1(int v){
  if(v>=n){
    return; 
  }
  int sz=(int)g[v].size(); 
  vector<int> pref(sz),suf(sz);
  for(int i=0;i<sz;i++){
    pref[i]=dp[g[v][i]];
    if(i){
      pref[i]*=pref[i-1];
      pref[i]%=mod;
    }
  }
  for(int i=sz-1;i>=0;i--){
    suf[i]=dp[g[v][i]];
    if(i!=sz-1){
      suf[i]*=suf[i+1];
      suf[i]%=mod;
    }
  }
  for(int i=0;i<sz;i++){
    int pr,sf; 
    pr=sf=1;
    if(i){
      pr=pref[i-1];
    }
    if(i!=sz-1){
      sf=suf[i+1];
    }
    dp1[g[v][i]]=dp1[v];
    dp1[g[v][i]]*=pr;
    dp1[g[v][i]]%=mod; 
    dp1[g[v][i]]*=sf;
    dp1[g[v][i]]%=mod; 
    dfs1(g[v][i]);
  }
}
ll sm(ll x,ll y){
  ll res=(x+y)%mod; 
  if(res<0){
    res+=mod;
  }
  return res;
}
ll ml(ll x,ll y){
  ll res=(x*y)%mod; 
  if(res<0){
    res+=mod;
  }
  return res; 
}
struct segtree{
    vector<ll> sums;
    vector<ll> lazy;
    int size;
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        sums.assign(2*size,0LL);
        lazy.assign(2*size,1LL);
    }
    void build(int x,int lx,int rx,vector<int> &a){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                sums[x]=a[lx];
            }
            return;
        }
        int m=(lx+rx)/2;
        build(2*x+1,lx,m,a);
        build(2*x+2,m,rx,a);
        sums[x]=sm(sums[2*x+1],sums[2*x+2]);
    }
    void build(vector<int> &a){
        build(0,0,size,a);
    }
    void propogate(int x,int lx,int rx){
        if(rx-lx==1){
            return;
        }
        sums[2*x+1]=ml(sums[2*x+1],lazy[x]);
        sums[2*x+2]=ml(sums[2*x+2],lazy[x]);
        lazy[2*x+1]=ml(lazy[2*x+1],lazy[x]);
        lazy[2*x+2]=ml(lazy[2*x+2],lazy[x]);
        lazy[x]=1;
    }
    void upd(int x,int lx,int rx,int l,int r,int v){
        propogate(x,lx,rx);
        if(rx<=l || lx>=r){
            return;
        }
        if(lx>=l && rx<=r){
            sums[x]=ml(sums[x],v);
            lazy[x]=ml(lazy[x],v);
            return;
        }
        int m=(lx+rx)/2;
        upd(2*x+1,lx,m,l,r,v);
        upd(2*x+2,m,rx,l,r,v);
        sums[x]=sm(sums[2*x+1],sums[2*x+2]);
    }
    void upd(int l,int r,int v){
        return upd(0,0,size,l,r,v);
    }
    ll get(int x,int lx,int rx,int l,int r){
        propogate(x,lx,rx);
        if(rx<=l || lx>=r){
            return 0;
        }
        if(lx>=l && rx<=r){
            return sums[x];
        }
        int m=(lx+rx)/2;
        ll s1,s2;
        s1=get(2*x+1,lx,m,l,r);
        s2=get(2*x+2,m,rx,l,r);
        return sm(s1,s2);
    }
    ll get(int l,int r){
        return get(0,0,size,l,r);
    }
};
segtree st;
ll res=0;
void init(int N, int M, vector<int> P, vector<int> A) {
  n=N; 
  m=M; 
  g.resize(n+m);
  for(int i=1;i<n+m;i++){
    g[P[i]].push_back(i);
  }
  dfs(0);
  dp1[0]=1;
  dfs1(0);
  st.init(m);
  vector<int> b;
  for(int i=0;i<m;i++){
    if(A[i]){
      res=sm(res,dp1[n+i]);
      b.push_back(-dp1[n+i]);
    }
    else{
      b.push_back(dp1[n+i]);
    }
  }
  st.build(b);
}
int count_ways(int L, int R) {
  res=sm(res,st.get(L-n,R-n+1));
  res%=mod;
  st.upd(L-n,R-n+1,-1);
  return res;
}

Subtask #1
2.0 / 2.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 0 ms 2392 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 0 ms 2392 KB Output is correct
9 Correct 0 ms 2648 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 0 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 0 ms 2392 KB Output is correct
9 Correct 0 ms 2392 KB Output is correct
10 Correct 0 ms 2392 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 0 ms 2392 KB Output is correct
14 Correct 0 ms 2392 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 0 ms 2392 KB Output is correct
17 Correct 0 ms 2648 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2648 KB Output is correct
20 Correct 1 ms 2392 KB Output is correct
21 Incorrect 1 ms 2392 KB 1st lines differ - on the 1st token, expected: '759476520', found: '110486194'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 7256 KB Output is correct
2 Correct 645 ms 12120 KB Output is correct
3 Correct 643 ms 12120 KB Output is correct
4 Correct 604 ms 12120 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 7256 KB Output is correct
2 Correct 645 ms 12120 KB Output is correct
3 Correct 643 ms 12120 KB Output is correct
4 Correct 604 ms 12120 KB Output is correct
5 Correct 542 ms 7256 KB Output is correct
6 Correct 661 ms 12120 KB Output is correct
7 Correct 703 ms 12120 KB Output is correct
8 Correct 662 ms 12120 KB Output is correct
9 Correct 288 ms 2648 KB Output is correct
10 Correct 626 ms 2904 KB Output is correct
11 Correct 506 ms 2904 KB Output is correct
12 Correct 542 ms 2904 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 0 ms 2392 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 0 ms 2392 KB Output is correct
9 Correct 0 ms 2648 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 423 ms 7256 KB Output is correct
14 Correct 645 ms 12120 KB Output is correct
15 Correct 643 ms 12120 KB Output is correct
16 Correct 604 ms 12120 KB Output is correct
17 Correct 542 ms 7256 KB Output is correct
18 Correct 661 ms 12120 KB Output is correct
19 Correct 703 ms 12120 KB Output is correct
20 Correct 662 ms 12120 KB Output is correct
21 Correct 288 ms 2648 KB Output is correct
22 Correct 626 ms 2904 KB Output is correct
23 Correct 506 ms 2904 KB Output is correct
24 Correct 542 ms 2904 KB Output is correct
25 Correct 677 ms 18256 KB Output is correct
26 Correct 749 ms 18492 KB Output is correct
27 Correct 736 ms 18384 KB Output is correct
28 Correct 554 ms 18384 KB Output is correct
29 Correct 727 ms 33872 KB Output is correct
30 Correct 608 ms 33872 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 0 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 0 ms 2392 KB Output is correct
9 Correct 0 ms 2392 KB Output is correct
10 Correct 0 ms 2392 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 0 ms 2392 KB Output is correct
14 Correct 0 ms 2392 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 0 ms 2392 KB Output is correct
17 Correct 0 ms 2648 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2648 KB Output is correct
20 Correct 1 ms 2392 KB Output is correct
21 Incorrect 1 ms 2392 KB 1st lines differ - on the 1st token, expected: '759476520', found: '110486194'
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 0 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 0 ms 2392 KB Output is correct
9 Correct 0 ms 2392 KB Output is correct
10 Correct 0 ms 2392 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 0 ms 2392 KB Output is correct
14 Correct 0 ms 2392 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 0 ms 2392 KB Output is correct
17 Correct 0 ms 2648 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2648 KB Output is correct
20 Correct 1 ms 2392 KB Output is correct
21 Incorrect 1 ms 2392 KB 1st lines differ - on the 1st token, expected: '759476520', found: '110486194'
22 Halted 0 ms 0 KB -