oj.uz

Submission #830976

# Submission time Handle Problem Language Result Execution time Memory
830976 2023-08-19T14:21:22 Z beaconmc Digital Circuit (IOI22_circuit) C++17
2 / 100
 378 ms 18628 KB 
#include "circuit.h"


#include <bits/stdc++.h>

typedef long long ll;
using namespace std;


#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


vector<ll> edges[100001];
ll possible[100001];
ll contrib[100001];
ll dps[100001];
vector<int> p;
bool state[100001];



int initdfs(ll a){
  if (edges[a].size() == 0) return possible[a] = 1;

  ll temp = 1;
  for (auto&i : edges[a]){
    temp *= initdfs(i);
    temp %= 1000002022;
  }
  temp *= edges[a].size();
  temp %= 1000002022;


  return possible[a] = temp;
}

int dp(ll a){
  if (a==0) return 1;
  if (dps[a] != -1) return dps[a];

  ll temp = 1;

  for (auto&i : edges[p[a]]){
    if (i != a) temp *= possible[i];
    temp %= 1000002022;
  }
  dps[a] = temp * dp(p[a]) % 1000002022;
  return dps[a];
}

ll n,m;



const ll NN = 1<<18;
ll tree[NN*2];
ll actual[NN*2];
ll lazy[NN*2];

int actupd(ll a, ll b, ll val, ll k=1, ll x = 0, ll y = NN-1){

  if (b<x || a>y) return actual[k];
  if (a<=x && y<=b){

    actual[k] += val;
    return actual[k];
  }
  ll mid = (x+y)/2;


  actual[k] =  actupd(a,b,val,k*2, x, mid) + actupd(a,b,val,k*2+1, mid+1, y);

  return actual[k];
}


void prop(ll k){
  lazy[k*2] += lazy[k];
  lazy[k*2+1] += lazy[k];
  if (lazy[k] %2==1){
    tree[k] = (actual[k] - tree[k]+1000002022)%1000002022;
  }
  lazy[k] = 0;
}


int upd(ll a, ll b, ll k=1, ll x = 0, ll y = NN-1){
  if (b<x || a>y) return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022);
  if (a<=x && y<=b){
    lazy[k] += 1;
    return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022);
  }
  ll mid = (x+y)/2;
  prop(k);

  tree[k] = upd(a,b,k*2, x, mid) + upd(a,b,k*2+1, mid+1, y);
  return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022);
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
  FOR(i,0,100001) dps[i] = -1;
  FOR(i,0,NN*2) tree[i] = 0, actual[i] = 0, lazy[i] = 0;
  p = P;
  n = N;
  m = M;
  FOR(i,1,N+M){
    edges[P[i]].push_back(i);
  }
  FOR(i,N,N+M){
    state[i] = A[i-N];
  }
  initdfs(0);


  FOR(i,N,N+M){
    ll temp = possible[i];
    temp *= dp(i);
    contrib[i] = temp%1000002022;
  }
  FOR(i,n,n+m){
    actupd(i-n+1, i-n+1, contrib[i]);
  }
  FOR(i,0,NN*2) tree[i] = actual[i];
  FOR(i,n,n+m){
    if (A[i-n] == 0){
      upd(i-n+1, i-n+1);
    }
  }


}





int count_ways(int L, int R) {
  upd(L-n+1, R-n+1);


  return lazy[1]%2==0 ? tree[1] : ((actual[1] - tree[1]+1000002022)%1000002022);

}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15696 KB Output is correct
2 Correct 7 ms 15696 KB Output is correct
3 Correct 10 ms 15696 KB Output is correct
4 Correct 11 ms 15800 KB Output is correct
5 Correct 11 ms 15800 KB Output is correct
6 Correct 12 ms 15808 KB Output is correct
7 Correct 11 ms 15696 KB Output is correct
8 Correct 11 ms 15696 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15696 KB Output is correct
2 Incorrect 6 ms 15696 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 7 ms 15696 KB Output is correct
2 Correct 7 ms 15696 KB Output is correct
3 Correct 10 ms 15696 KB Output is correct
4 Correct 11 ms 15800 KB Output is correct
5 Correct 11 ms 15800 KB Output is correct
6 Correct 12 ms 15808 KB Output is correct
7 Correct 11 ms 15696 KB Output is correct
8 Correct 11 ms 15696 KB Output is correct
9 Correct 8 ms 15696 KB Output is correct
10 Incorrect 6 ms 15696 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 378 ms 18628 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 378 ms 18628 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 8 ms 15696 KB Output is correct
2 Incorrect 6 ms 15696 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 7 ms 15696 KB Output is correct
2 Correct 7 ms 15696 KB Output is correct
3 Correct 10 ms 15696 KB Output is correct
4 Correct 11 ms 15800 KB Output is correct
5 Correct 11 ms 15800 KB Output is correct
6 Correct 12 ms 15808 KB Output is correct
7 Correct 11 ms 15696 KB Output is correct
8 Correct 11 ms 15696 KB Output is correct
9 Correct 8 ms 15696 KB Output is correct
10 Incorrect 6 ms 15696 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 7 ms 15696 KB Output is correct
2 Correct 7 ms 15696 KB Output is correct
3 Correct 10 ms 15696 KB Output is correct
4 Correct 11 ms 15800 KB Output is correct
5 Correct 11 ms 15800 KB Output is correct
6 Correct 12 ms 15808 KB Output is correct
7 Correct 11 ms 15696 KB Output is correct
8 Correct 11 ms 15696 KB Output is correct
9 Correct 8 ms 15696 KB Output is correct
10 Incorrect 6 ms 15696 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
11 Halted 0 ms 0 KB -