Submission #1058041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058041		aykhn	Digital Circuit (IOI22_circuit)	C++17	100 / 100	730 ms	50996 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];

void dfs(int a, int cur)
{
  if (adj[a].empty())
  {
    val[a] = cur;
    return;
  }
  vector<int> pre(adj[a].size()), suf(adj[a].size());
  for (int i = 0; i < adj[a].size(); i++)
  {
    pre[i] = (i ? pre[i - 1] : 1LL);
    pre[i] = (pre[i] * way[adj[a][i]]) % mod;
  }
  for (int i = (int)adj[a].size() - 1; i >= 0; i--)
  {
    suf[i] = (i + 1 < adj[a].size() ? suf[i + 1] : 1LL);
    suf[i] = (suf[i] * way[adj[a][i]]) % mod;
  }
  for (int i = 0; i < adj[a].size(); i++)
  {
    int A = (i ? pre[i - 1] : 1LL), B = (i + 1 < adj[a].size() ? suf[i + 1] : 1LL);
    dfs(adj[a][i], (((cur * A) % mod) * B) % mod);
  }
}

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);
  dfs(0, 1);
  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];
}

Compilation message (stderr)

circuit.cpp: In function 'void dfs(long long int, long long int)':
circuit.cpp:42:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (int i = 0; i < adj[a].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~
circuit.cpp:49:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     suf[i] = (i + 1 < adj[a].size() ? suf[i + 1] : 1LL);
      |               ~~~~~~^~~~~~~~~~~~~~~
circuit.cpp:52:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int i = 0; i < adj[a].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~
circuit.cpp:54:48: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     int A = (i ? pre[i - 1] : 1LL), B = (i + 1 < adj[a].size() ? suf[i + 1] : 1LL);
      |                                          ~~~~~~^~~~~~~~~~~~~~~

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