Submission #1058023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058023		aykhn	Digital Circuit (IOI22_circuit)	C++17	62 / 100	3062 ms	26872 KiB

circuit

#include <bits/stdc++.h>
#include "circuit.h"
 
using namespace std;
 
#define int long long
 
const int MXN = 2e5 + 5;
const int mod = 1e9 + 2022;
 
int n, m, res = 0;
vector<int> A, P;
vector<int> adj[MXN];
int dp[2][MXN], SZ[MXN];
int way[MXN];
 
void _init(int a)
{
  if (adj[a].empty())
  {
    way[a] = 1;
    return;
  }
  way[a] = adj[a].size();
  for (int &v : adj[a])
  {
    _init(v);
    way[a] = (way[a] * way[v]) % mod;
  }
}

int val[MXN];
array<int, 2> st[MXN << 2];
int lz[MXN << 2];

void relax(int l, int r, int x)
{
  if (!lz[x]) return;
  swap(st[x][0], st[x][1]);
  if (l == r)
  {
    lz[x] = 0;
    return;
  }
  lz[2*x] ^= lz[x], lz[2*x + 1] ^= lz[x];
  lz[x] = 0;
}

void upd(int l, int r, int x, int lx, int rx)
{
  relax(l, r, x);
  if (l > rx || r < lx) return;
  if (l >= lx && r <= rx)
  {
    lz[x] ^= 1;
    relax(l, r, x);
    return;
  }
  int mid = (l + r) >> 1;
  upd(l, mid, 2*x, lx, rx);
  upd(mid + 1, r, 2*x + 1, lx, rx);
  st[x][0] = (st[2*x][0] + st[2*x + 1][0]) % mod;
  st[x][1] = (st[2*x][1] + st[2*x + 1][1]) % mod;
}

void build(int l, int r, int x)
{
  if (l == r)
  {
    st[x][0] = A[l] * val[l];
    st[x][1] = (A[l] ^ 1) * val[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, 2*x);
  build(mid + 1, r, 2*x + 1);
  st[x][0] = (st[2*x][0] + st[2*x + 1][0]) % mod;
  st[x][1] = (st[2*x][1] + st[2*x + 1][1]) % mod;
}
 
void init(int32_t N, int32_t M, vector<int32_t> PP, vector<int32_t> AA) 
{
  n = N, m = M;
  for (int32_t &i : PP) P.push_back(i);
  for (int32_t &i : AA) A.push_back(i);
  reverse(A.begin(), A.end());
  A.resize(N + M, 0);
  reverse(A.begin(), A.end());
  for (int i = 1; i < N + M; i++) adj[P[i]].push_back(i);
  _init(0);
  for (int i = N; i < N + M; i++)
  {
    int x = i;
    val[i] = 1;
    while (P[x] != -1)
    {
      for (int &v : adj[P[x]])
      {
        if (v == x) continue;
        val[i] = (val[i] * way[v]) % mod;
      }
      x = P[x];
    }
  }
  build(N, N + M - 1, 1);
}
 
int32_t count_ways(int32_t L, int32_t R) {
  upd(n, n + m - 1, 1, L, R);
  return st[1][0];
}

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