Submission #813110

#	Time	Username	Problem	Language	Result	Execution time	Memory
813110		kwongweng	Digital Circuit (IOI22_circuit)	C++17	46 / 100	2918 ms	20916 KiB

circuit

#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;
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,n+m) cout << prod[i] << " ";
  //cout << '\n';
  //FOR(i,0,m) cout << b[i] << " ";
  //cout << '\n';
  FOR(i,0,m){
    if (a[i]){ans += b[i]; ans %= MOD;}
  }
}

int count_ways(int L, int R) {
  FOR(i,L-n,R+1-n){
    if (a[i]){
      ans+=MOD-b[i]; ans %= MOD;
    }else{
      ans+=b[i]; ans %= MOD;
    }
    a[i]=1-a[i];
  }
  return ans;
}

• 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: 28 / 28
• Subtask 8: 0 / 11