oj.uz

Submission #813213

# Submission time Handle Problem Language Result Execution time Memory
813213 2023-08-07T14:18:50 Z kwongweng Digital Circuit (IOI22_circuit) C++17
46 / 100
 835 ms 20956 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second

ll MOD = 1e9 + 2022;
int n, m;
vi g[200000];
vector<ll> prod(100000);
vector<ll> b(100000);
vi a;

void get_prod(int u){
  prod[u]=max(1,(int)g[u].size());
  for (int v : g[u]){
    get_prod(v);
    prod[u] *= prod[v]; prod[u] %= MOD;
  }
}

void dfs(int u, ll val){
  int len = g[u].size();
  if (len==0){
    b[u-n] = val; return;
  }
  vector<ll> p(len);
  FOR(i,0,len){
    p[i] = prod[g[u][i]];
  }
  vector<ll> pre(len+1), suf(len+1);
  pre[0]=1; FOR(i,1,len+1){
    pre[i]=(pre[i-1]*p[i-1]) % MOD;
  }
  suf[len]=1; ROF(i,len-1,0){
    suf[i]=(suf[i+1]*p[i]) % MOD;
  }
  FOR(i,0,len){
    int v = g[u][i];
    ll Val = (pre[i]*suf[i+1]) % MOD;
    Val *= val; Val %= MOD;
    dfs(v,Val);
  }
}

ll ans=0;
struct segtree{
  int sz; vi neg; vector<ll> sm;
  void build(int v, int tl, int tr){
    if (tl==tr){
      if (a[tl]==0) sm[v]=MOD-b[tl];
      else sm[v]=b[tl];
      return;
    }
    int tm = (tl+tr)/2;
    build(2*v,tl,tm); build(2*v+1,tm+1,tr);
    sm[v]=(sm[2*v]+sm[2*v+1]) % MOD;
  }
  void init(int n){
    sz=n; neg.assign(4*n,1); sm.assign(4*n,0);
    build(1,0,sz-1);
  }
  void update(int v, int tl, int tr, int l, int r){
    if (tl != tr && neg[v]==-1){
      neg[2*v]=-neg[2*v]; sm[2*v]=MOD-sm[2*v];
      neg[2*v+1]=-neg[2*v+1]; sm[2*v+1]=MOD-sm[2*v+1];
      neg[v]=1;
    }
    if (tl==l && tr==r){
      neg[v]=-neg[v]; sm[v]=MOD-sm[v]; return;
    }
    if (l>r) return;
    int tm = (tl+tr)/2;
    update(2*v,tl,tm,l,min(r,tm)); update(2*v+1,tm+1,tr,max(l,tm+1),r);
    sm[v]=(sm[2*v]+sm[2*v+1]) % MOD;
  }
  void update(int l, int r){update(1,0,sz-1,l,r);}

  ll get(int v, int tl, int tr, int l, int r){
    if (tl != tr && neg[v]==-1){
      neg[2*v]=-neg[2*v]; sm[2*v]=MOD-sm[2*v];
      neg[2*v+1]=-neg[2*v+1]; sm[2*v+1]=MOD-sm[2*v+1];
      neg[v]=1;
    }
    if (tl==l && tr==r) return sm[v];
    if (l>r) return 0;
    int tm = (tl+tr)/2;
    ll val = (get(2*v,tl,tm,l,min(r,tm))+get(2*v+1,tm+1,tr,max(l,tm+1),r)) % MOD;
    sm[v]=(sm[2*v]+sm[2*v+1])%MOD;
    return val;
  }

  ll get(int l, int r){return get(1,0,sz-1,l,r);}
};

segtree st;

void init(int N, int M, vi P, vi A) {
  n=N, m=M; a=A;
  FOR(i,1,n+m){
    g[P[i]].pb(i);
  }
  get_prod(0); dfs(0,1);
  //FOR(i,0,m) cout << a[i] << " ";
  //cout << '\n';
  //FOR(i,0,m) cout << b[i] << " ";
  //cout << '\n';
  st.init(m);
  FOR(i,0,m){
    if (a[i]){ans += b[i]; ans %= MOD;}
  }
}

int count_ways(int L, int R) {
  st.update(L-n,R-n);
  //FOR(i,0,m) cout << st.get(i,i) << " ";
  //cout << '\n';
  ans += st.get(L-n,R-n);
  ans %= MOD;
  return ans;
}

Subtask #1
2.0 / 2.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 3 ms 6608 KB Output is correct
3 Correct 3 ms 6736 KB Output is correct
4 Correct 3 ms 6608 KB Output is correct
5 Correct 4 ms 6608 KB Output is correct
6 Correct 3 ms 6628 KB Output is correct
7 Correct 3 ms 6608 KB Output is correct
8 Correct 3 ms 6608 KB Output is correct
9 Correct 3 ms 6608 KB Output is correct
10 Correct 3 ms 6864 KB Output is correct
11 Correct 3 ms 6864 KB Output is correct
12 Correct 3 ms 6608 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6480 KB Output is correct
2 Correct 3 ms 6480 KB Output is correct
3 Correct 3 ms 6608 KB Output is correct
4 Correct 3 ms 6652 KB Output is correct
5 Correct 3 ms 6608 KB Output is correct
6 Correct 3 ms 6608 KB Output is correct
7 Correct 3 ms 6608 KB Output is correct
8 Correct 3 ms 6608 KB Output is correct
9 Correct 3 ms 6480 KB Output is correct
10 Correct 3 ms 6608 KB Output is correct
11 Correct 3 ms 6736 KB Output is correct
12 Correct 3 ms 6608 KB Output is correct
13 Correct 4 ms 6608 KB Output is correct
14 Correct 3 ms 6628 KB Output is correct
15 Correct 3 ms 6608 KB Output is correct
16 Correct 3 ms 6608 KB Output is correct
17 Correct 3 ms 6608 KB Output is correct
18 Correct 3 ms 6864 KB Output is correct
19 Correct 3 ms 6864 KB Output is correct
20 Correct 3 ms 6608 KB Output is correct
21 Correct 3 ms 6608 KB Output is correct
22 Correct 4 ms 6644 KB Output is correct
23 Correct 4 ms 6628 KB Output is correct
24 Correct 4 ms 6608 KB Output is correct
25 Correct 4 ms 6592 KB Output is correct
26 Correct 3 ms 6608 KB Output is correct
27 Correct 5 ms 6736 KB Output is correct
28 Correct 3 ms 6608 KB Output is correct
29 Correct 3 ms 6656 KB Output is correct
30 Correct 3 ms 6608 KB Output is correct
31 Correct 4 ms 6864 KB Output is correct
32 Correct 4 ms 6608 KB Output is correct
33 Correct 4 ms 6608 KB Output is correct
34 Correct 4 ms 6608 KB Output is correct
35 Correct 3 ms 6608 KB Output is correct
36 Correct 3 ms 6864 KB Output is correct
37 Correct 3 ms 6884 KB Output is correct
38 Correct 4 ms 6864 KB Output is correct
39 Correct 4 ms 6628 KB Output is correct
40 Correct 3 ms 6608 KB Output is correct
41 Correct 4 ms 6608 KB Output is correct
42 Correct 4 ms 6668 KB Output is correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 10032 KB Output is correct
2 Runtime error 41 ms 20956 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 10032 KB Output is correct
2 Runtime error 41 ms 20956 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 3 ms 6608 KB Output is correct
3 Correct 3 ms 6736 KB Output is correct
4 Correct 3 ms 6608 KB Output is correct
5 Correct 4 ms 6608 KB Output is correct
6 Correct 3 ms 6628 KB Output is correct
7 Correct 3 ms 6608 KB Output is correct
8 Correct 3 ms 6608 KB Output is correct
9 Correct 3 ms 6608 KB Output is correct
10 Correct 3 ms 6864 KB Output is correct
11 Correct 3 ms 6864 KB Output is correct
12 Correct 3 ms 6608 KB Output is correct
13 Correct 473 ms 10032 KB Output is correct
14 Runtime error 41 ms 20956 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6480 KB Output is correct
2 Correct 3 ms 6480 KB Output is correct
3 Correct 3 ms 6608 KB Output is correct
4 Correct 3 ms 6652 KB Output is correct
5 Correct 3 ms 6608 KB Output is correct
6 Correct 3 ms 6608 KB Output is correct
7 Correct 3 ms 6608 KB Output is correct
8 Correct 3 ms 6608 KB Output is correct
9 Correct 3 ms 6480 KB Output is correct
10 Correct 3 ms 6608 KB Output is correct
11 Correct 3 ms 6736 KB Output is correct
12 Correct 3 ms 6608 KB Output is correct
13 Correct 4 ms 6608 KB Output is correct
14 Correct 3 ms 6628 KB Output is correct
15 Correct 3 ms 6608 KB Output is correct
16 Correct 3 ms 6608 KB Output is correct
17 Correct 3 ms 6608 KB Output is correct
18 Correct 3 ms 6864 KB Output is correct
19 Correct 3 ms 6864 KB Output is correct
20 Correct 3 ms 6608 KB Output is correct
21 Correct 3 ms 6608 KB Output is correct
22 Correct 4 ms 6644 KB Output is correct
23 Correct 4 ms 6628 KB Output is correct
24 Correct 4 ms 6608 KB Output is correct
25 Correct 4 ms 6592 KB Output is correct
26 Correct 3 ms 6608 KB Output is correct
27 Correct 5 ms 6736 KB Output is correct
28 Correct 3 ms 6608 KB Output is correct
29 Correct 3 ms 6656 KB Output is correct
30 Correct 3 ms 6608 KB Output is correct
31 Correct 4 ms 6864 KB Output is correct
32 Correct 4 ms 6608 KB Output is correct
33 Correct 4 ms 6608 KB Output is correct
34 Correct 4 ms 6608 KB Output is correct
35 Correct 3 ms 6608 KB Output is correct
36 Correct 3 ms 6864 KB Output is correct
37 Correct 3 ms 6884 KB Output is correct
38 Correct 4 ms 6864 KB Output is correct
39 Correct 4 ms 6628 KB Output is correct
40 Correct 3 ms 6608 KB Output is correct
41 Correct 4 ms 6608 KB Output is correct
42 Correct 4 ms 6668 KB Output is correct
43 Correct 426 ms 6864 KB Output is correct
44 Correct 814 ms 6888 KB Output is correct
45 Correct 646 ms 6880 KB Output is correct
46 Correct 835 ms 7100 KB Output is correct
47 Correct 807 ms 7120 KB Output is correct
48 Correct 827 ms 7096 KB Output is correct
49 Correct 750 ms 7096 KB Output is correct
50 Correct 666 ms 7100 KB Output is correct
51 Correct 635 ms 6992 KB Output is correct
52 Correct 775 ms 6992 KB Output is correct
53 Correct 784 ms 8164 KB Output is correct
54 Correct 719 ms 7092 KB Output is correct
55 Correct 629 ms 7000 KB Output is correct
56 Correct 732 ms 6988 KB Output is correct
57 Correct 807 ms 6916 KB Output is correct
58 Correct 729 ms 8260 KB Output is correct
59 Correct 630 ms 8400 KB Output is correct
60 Correct 698 ms 8400 KB Output is correct
61 Correct 693 ms 7160 KB Output is correct
62 Correct 740 ms 6884 KB Output is correct
63 Correct 727 ms 6868 KB Output is correct
64 Correct 759 ms 6992 KB Output is correct
65 Correct 317 ms 6776 KB Output is correct
66 Correct 747 ms 6992 KB Output is correct
67 Correct 729 ms 6992 KB Output is correct
68 Correct 639 ms 7000 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6480 KB Output is correct
2 Correct 3 ms 6480 KB Output is correct
3 Correct 3 ms 6608 KB Output is correct
4 Correct 3 ms 6652 KB Output is correct
5 Correct 3 ms 6608 KB Output is correct
6 Correct 3 ms 6608 KB Output is correct
7 Correct 3 ms 6608 KB Output is correct
8 Correct 3 ms 6608 KB Output is correct
9 Correct 3 ms 6480 KB Output is correct
10 Correct 3 ms 6608 KB Output is correct
11 Correct 3 ms 6736 KB Output is correct
12 Correct 3 ms 6608 KB Output is correct
13 Correct 4 ms 6608 KB Output is correct
14 Correct 3 ms 6628 KB Output is correct
15 Correct 3 ms 6608 KB Output is correct
16 Correct 3 ms 6608 KB Output is correct
17 Correct 3 ms 6608 KB Output is correct
18 Correct 3 ms 6864 KB Output is correct
19 Correct 3 ms 6864 KB Output is correct
20 Correct 3 ms 6608 KB Output is correct
21 Correct 3 ms 6608 KB Output is correct
22 Correct 4 ms 6644 KB Output is correct
23 Correct 4 ms 6628 KB Output is correct
24 Correct 4 ms 6608 KB Output is correct
25 Correct 4 ms 6592 KB Output is correct
26 Correct 3 ms 6608 KB Output is correct
27 Correct 5 ms 6736 KB Output is correct
28 Correct 3 ms 6608 KB Output is correct
29 Correct 3 ms 6656 KB Output is correct
30 Correct 3 ms 6608 KB Output is correct
31 Correct 4 ms 6864 KB Output is correct
32 Correct 4 ms 6608 KB Output is correct
33 Correct 4 ms 6608 KB Output is correct
34 Correct 4 ms 6608 KB Output is correct
35 Correct 3 ms 6608 KB Output is correct
36 Correct 3 ms 6864 KB Output is correct
37 Correct 3 ms 6884 KB Output is correct
38 Correct 4 ms 6864 KB Output is correct
39 Correct 4 ms 6628 KB Output is correct
40 Correct 3 ms 6608 KB Output is correct
41 Correct 4 ms 6608 KB Output is correct
42 Correct 4 ms 6668 KB Output is correct
43 Correct 473 ms 10032 KB Output is correct
44 Runtime error 41 ms 20956 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -