oj.uz

Submission #914585

# Submission time Handle Problem Language Result Execution time Memory
914585 2024-01-22T11:01:16 Z cig32 Digital Circuit (IOI22_circuit) C++17
4 / 100
 666 ms 14936 KB 
#include "circuit.h"
#include "bits/stdc++.h"
using namespace std;
#define int long long

#include <vector>

const int MAXN = 2e5 + 12;
const int MOD = 1e9 + 2022;
int n, m;
vector<int> adj[MAXN];
int contrib[MAXN];
int ans;
int a[MAXN];
int lazy[MAXN];
int Y[MAXN];
const int S = 320;
int sum[S];
int state[S];
int tot[S];
void calc_y(int node) {
  Y[node] = adj[node].size();
  Y[node] = max(1ll, Y[node]);
  for(int x: adj[node]) {
    calc_y(x);
    Y[node] *= Y[x];
    Y[node] %= MOD;
  }
}
void propagate(int node) {
  for(int x: adj[node]) {
    lazy[x] *= lazy[node];
    lazy[x] %= MOD;
    propagate(x);
  }
}
void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
  for(int i=0; i<M; i++) contrib[i] = 1;
  for(int i=1; i<N+M; i++) adj[P[i]].push_back(i);
  for(int i=0; i<M; i++) a[i] = A[i];
  n = N;
  m = M;
  ans = 0;
  calc_y(0);
  for(int i=0; i<N+M; i++) lazy[i] = 1;
  for(int i=0; i<N; i++) {
    int len = adj[i].size();
    int pre[len], suf[len];
    for(int j=0; j<len; j++) {
      pre[j] = Y[adj[i][j]];
      suf[j] = Y[adj[i][j]];
    }
    for(int j=1; j<len; j++) {
      pre[j] *= pre[j-1];
      pre[j] %= MOD;
    }
    for(int j=len-2; j>=0; j--) {
      suf[j] *= suf[j+1];
      suf[j] %= MOD;
    }
    for(int j=0; j<len; j++) {
      if(j > 0) lazy[adj[i][j]] *= pre[j-1];
      lazy[adj[i][j]] %= MOD;
      if(j + 1 < len) lazy[adj[i][j]] *= suf[j+1];
      lazy[adj[i][j]] %= MOD;
    }
  }
  propagate(0);
  for(int i=0; i<N+M; i++) {
    contrib[i] = lazy[i];
  }
  for(int i=0; i<M; i++) {
    sum[i / S] += a[i] * contrib[i + N];
    sum[i / S] %= MOD;
    state[i / S] = 0;
    tot[i / S] += contrib[i + N];
    tot[i / S] %= MOD;
  }
  for(int i=N; i<N+M; i++) {
    if(a[i-N]) ans = (ans + contrib[i]) % MOD;
  }
}

int32_t count_ways(int32_t L, int32_t R) {
  L -= n;
  R -= n;
  if(R - L <= 2 * S) {
    for(int i=L; i<=R; i++) {
      int og = a[i] ^ state[i / S];
      a[i] ^= 1;
      ans += MOD - og * contrib[i + n];
      ans %= MOD;
      sum[i / S] += MOD - og * contrib[i + n];
      sum[i / S] %= MOD;
      og ^= 1;
      ans += og * contrib[i + n];
      ans %= MOD;
      sum[i / S] += og * contrib[i + n];
      sum[i / S] %= MOD;
    }
    return ans;
  }
  while(L % S != 0) {
    int i = L;
    int og = a[i] ^ state[i / S];
    a[i] ^= 1;
    ans += MOD - og * contrib[i + n];
    ans %= MOD;
    sum[i / S] += MOD - og * contrib[i + n];
    sum[i / S] %= MOD;
    og ^= 1;
    ans += og * contrib[i + n];
    ans %= MOD;
    sum[i / S] += og * contrib[i + n];
    sum[i / S] %= MOD;
    L++;
  }
  while(R % S != S - 1) {
    int i = R;
    int og = a[i] ^ state[i / S];
    a[i] ^= 1;
    ans += MOD - og * contrib[i + n];
    ans %= MOD;
    sum[i / S] += MOD - og * contrib[i + n];
    sum[i / S] %= MOD;
    og ^= 1;
    ans += og * contrib[i + n];
    ans %= MOD;
    sum[i / S] += og * contrib[i + n];
    sum[i / S] %= MOD;
    R--;
  }
  for(int i=L; i<=R; i+=S) {
    if(state[i / S]) {
      ans += MOD - sum[i / S];
      ans %= MOD;
    }
    else {
      ans += MOD + sum[i / S] - tot[i / S];
      ans %= MOD;
    }
    state[i / S] ^= 1;
    if(state[i / S]) {
      ans += sum[i / S];
      ans %= MOD;
    }
    else {
      ans += MOD + tot[i / S] - sum[i / S];
      ans %= MOD;
    }
  }
  return ans;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 4 ms 11096 KB Output is correct
3 Correct 3 ms 11096 KB Output is correct
4 Correct 3 ms 11096 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 3 ms 11096 KB Output is correct
7 Incorrect 3 ms 11096 KB 1st lines differ - on the 1st token, expected: '517', found: '425'
8 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11096 KB Output is correct
2 Correct 3 ms 11096 KB Output is correct
3 Correct 3 ms 11096 KB Output is correct
4 Correct 3 ms 11096 KB Output is correct
5 Correct 2 ms 11096 KB Output is correct
6 Correct 4 ms 11096 KB Output is correct
7 Incorrect 3 ms 11092 KB 1st lines differ - on the 1st token, expected: '942041994', found: '552874508'
8 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 4 ms 11096 KB Output is correct
3 Correct 3 ms 11096 KB Output is correct
4 Correct 3 ms 11096 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 3 ms 11096 KB Output is correct
7 Incorrect 3 ms 11096 KB 1st lines differ - on the 1st token, expected: '517', found: '425'
8 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 13160 KB Output is correct
2 Correct 531 ms 14936 KB Output is correct
3 Correct 551 ms 14820 KB Output is correct
4 Correct 500 ms 14936 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 13160 KB Output is correct
2 Correct 531 ms 14936 KB Output is correct
3 Correct 551 ms 14820 KB Output is correct
4 Correct 500 ms 14936 KB Output is correct
5 Incorrect 666 ms 13144 KB 1st lines differ - on the 1st token, expected: '105182172', found: '349172368'
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11096 KB Output is correct
2 Correct 3 ms 11096 KB Output is correct
3 Correct 3 ms 11096 KB Output is correct
4 Correct 3 ms 11096 KB Output is correct
5 Correct 2 ms 11096 KB Output is correct
6 Correct 4 ms 11096 KB Output is correct
7 Incorrect 3 ms 11092 KB 1st lines differ - on the 1st token, expected: '942041994', found: '552874508'
8 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 4 ms 11096 KB Output is correct
3 Correct 3 ms 11096 KB Output is correct
4 Correct 3 ms 11096 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 3 ms 11096 KB Output is correct
7 Incorrect 3 ms 11096 KB 1st lines differ - on the 1st token, expected: '517', found: '425'
8 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 4 ms 11096 KB Output is correct
3 Correct 3 ms 11096 KB Output is correct
4 Correct 3 ms 11096 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 3 ms 11096 KB Output is correct
7 Incorrect 3 ms 11096 KB 1st lines differ - on the 1st token, expected: '517', found: '425'
8 Halted 0 ms 0 KB -