Submission #1215076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215076		dosts	Digital Circuit (IOI22_circuit)	C++17	18 / 100	3051 ms	39920 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1'000'002'022, LIM = 1e6+1, inf = 2e9;

int add(int x,int y) {
    if ((x + y) >= MOD) return x + y - MOD;
    return x + y;
}

int mult(int x,int y) {
    return (1LL * x * y) % MOD;
}

int expo(int x,int y) {
  if (!y) return 1;
  int e = expo(x,y/2);
  e = mult(e,e);
  if (y&1) e= mult(e,x);
  return e;
}

vi edges[LIM],dp(LIM);
vector<int32_t> a;

int nn;
pii dfs(int node) {
  if (node >= nn) {
    dp[node] = a[node-nn];
    return {dp[node],1-dp[node]};
  }
  int sz = edges[node].size();
  vector<vi> dp2(sz+1,vi(sz+1,0));
  dp2[0][0] = 1;
  int cur = 0;
  for (auto it : edges[node]) {
    pii r = dfs(it);
    for (int j = 0;j<=cur;j++) {
      dp2[cur+1][j] = add(dp2[cur+1][j],mult(dp2[cur][j],r.ss));
      if (j<sz) dp2[cur+1][j+1] = add(dp2[cur+1][j+1],mult(dp2[cur][j],r.ff));
    }
    cur++;
  }
  int posible = 0,imposible = 0;
  for (int j = 0;j<=sz;j++) posible = add(posible,mult(dp2[sz][j],j));
  for (int j = 0;j<=sz;j++) imposible = add(imposible,mult(dp2[sz][j],sz-j));
  return {posible,imposible};
}
void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
  a = A;
  nn = N;
  for (int i=1;i<N+M;i++) edges[P[i]].push_back(i);
}

int32_t count_ways(int32_t L, int32_t R) {
  for (int i = L-nn;i<=R-nn;i++) a[i]^=1;
  return dfs(0).ff;
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11