Submission #1196130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196130		hyakup	Digital Circuit (IOI22_circuit)	C++20	2 / 100	222 ms	41648 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int n, m;
const int maxn = 2e5 + 10;
const int mod =  1000002022;

vector<int> adj[maxn];
vector<ll> pref[maxn], suf[maxn], fator(maxn);


ll dfs_init( int cur ){
  pref[cur].push_back(1);
  suf[cur].push_back(1);

  ll resp = max( (int)adj[cur].size(), 1 );

  for( int viz : adj[cur] ){
    ll tot = dfs_init( viz );
    resp *= tot;
    pref[cur].push_back(tot);
    suf[cur].push_back(tot);
  }
  pref[cur].push_back(1);
  suf[cur].push_back(1);

  for( int i = 1; i < (int)pref[cur].size(); i++ ) pref[cur][i] = (pref[cur][i - 1]*pref[cur][i])%mod;
  for( int i = (int)suf[cur].size() - 2; i >= 0; i-- ) suf[cur][i] = (suf[cur][i + 1]*suf[cur][i])%mod;

  return resp;
}

void dfs( int cur ){
  for( int i = 0; i < (int)adj[cur].size(); i++ ){
    int viz = adj[cur][i];
    fator[viz] = (((fator[cur]*pref[cur][i])%mod)*suf[cur][i + 2])%mod;
    dfs( viz );
  }
}

struct Node{
  ll v1 = 0, v2 = 0;
  bool lazy = false;
  Node( ll v1 = 0, ll v2 = 0 ) : v1(v1), v2(v2) {}
  Node operator + ( Node n ){
    return Node( (v1 + n.v1)%mod, (v2 + n.v2)%mod );
  }
} seg[4*maxn];

void build( int pos, int ini, int fim, vector<int> &a ){
  if( ini == fim ){
    seg[pos] = Node(fator[ini]*a[ini - n], fator[ini]*(1 - a[ini - n]) );
    return;
  }
  int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
  build( l, ini, mid, a ); build( r, mid + 1, fim, a );
  seg[pos] = seg[l] + seg[r];
}

void refresh( int pos, int ini, int fim ){
  if( !seg[pos].lazy ) return;
  seg[pos].lazy = false;
  swap( seg[pos].v1, seg[pos].v2 );
  if( ini == fim ) return;
  int l = 2*pos, r = 2*pos + 1;
  seg[l].lazy ^= true;
  seg[r].lazy ^= true;
}

void update( int pos, int ini, int fim, int ki, int kf ){
  refresh( pos, ini, fim );
  if( ki > fim || ini > kf ) return;
  if( ki <= ini && fim <= kf ){
    seg[pos].lazy = true; refresh( pos, ini, fim );
    return;
  }
  int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
  update( l, ini, mid, ki, kf ); update( r, mid + 1, fim, ki, kf );
  seg[pos] = seg[l] + seg[r];
}

void init( int N, int M, vector<int> P, vector<int> A ){
  n = N; m = M;
  for( int i = 1; i < n + m; i++ ) adj[P[i]].push_back(i);
  dfs_init(0);
  fator[0] = 1;
  dfs(0);

  build( 1, n, n + m - 1, A );
}


int count_ways(int l, int r) {
  update( 1, n, n + m - 1, l, r );

  return seg[1].v1;
}

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