Submission #1051173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051173		Trent	Digital Circuit (IOI22_circuit)	C++17	100 / 100	689 ms	49196 KiB

circuit

#include "circuit.h"
#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;

const ll MOD = 1000002022;
const int MN = 1e5 + 10;
vvi ch;
vll w;
int n, m;
vll totPos;
void sdfs(int c) {
  totPos[c] = c >= n ? 1 : ch[c].size();
  for(int i : ch[c]) {
    sdfs(i);
    totPos[c] = totPos[c] * totPos[i] % MOD;
  }
}
void dfs(int c, ll cw) {
  w[c] = cw;
  vll ppa(ch[c].size()), spa(ch[c].size()), val(ch[c].size());
  for(int j = 0; j < ch[c].size(); j++) {
    val[j] = totPos[ch[c][j]];
    ppa[j] = val[j] * (j == 0 ? 1 : ppa[j-1]) % MOD;
  }
  for(int j = (int) ch[c].size() - 1; j >= 0; --j) {
    spa[j] = val[j] * (j + 1 == ch[c].size() ? 1 : spa[j+1]) % MOD;
  }
  for(int i = 0; i < ch[c].size(); ++i) {
    ll wCh = cw * (i == 0 ? 1 : ppa[i-1]) % MOD * (i + 1 == ch[c].size() ? 1 : spa[i+1]) % MOD;
    dfs(ch[c][i], wCh);
  }
}

vb tgl;
struct node {
  ll tot, iTot;
  bool lz;
};
const int MM = 1e5 + 10, ME = 4 * MM;
node seg[ME];
void push(int c) {
  if(seg[c].lz) {
    if(2 * c + 1 < ME) {
      swap(seg[2*c].tot, seg[2*c].iTot);
      seg[2*c].lz = !seg[2*c].lz;
      swap(seg[2*c+1].tot, seg[2*c+1].iTot);
      seg[2*c+1].lz = !seg[2*c+1].lz;
    }
    seg[c].lz = false;
  }
}
void build(int v, int nl, int nr) {
  if(nl == nr) {
    if(tgl[nl + n]) seg[v].tot = w[nl+n], seg[v].iTot = 0;
    else seg[v].tot = 0, seg[v].iTot = w[nl+n];
  } else {
    int mid = (nl+nr)/2;
    build(2*v, nl, mid);
    build(2*v+1, mid+1, nr);
    seg[v].tot = (seg[2*v].tot+seg[2*v+1].tot) % MOD;
    seg[v].iTot = (seg[2*v].iTot+seg[2*v+1].iTot) % MOD;
  }
}
void upd(int v, int nl, int nr, int l, int r) {
  push(v);
  if(l > r) return;
  if(l == nl && r == nr) {
    swap(seg[v].tot, seg[v].iTot);
    assert(!seg[v].lz);
    seg[v].lz = true;
  } else {
    int mid = (nl+nr)/2;
    upd(2*v, nl, mid, l, min(mid, r));
    upd(2*v+1, mid+1, nr, max(mid+1,l), r);
    seg[v].tot = (seg[2*v].tot + seg[2*v+1].tot) % MOD;
    seg[v].iTot = (seg[2*v].iTot + seg[2*v+1].iTot) % MOD;
  }
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
  ::n = N, ::m = M;
  ch.resize(N+M);
  totPos.resize(N+M);
  w.resize(N+M);
  tgl.resize(N+M);

  REP(i, 1, N+M) ch[P[i]].push_back(i);
  sdfs(0);
  dfs(0, 1);
  forR(i, M) tgl[N+i] = A[i] == 1;
  build(1, 0, m-1);
}

int count_ways(int L, int R) {
  upd(1, 0, m-1, L-n, R-n);
  ll tot = seg[1].tot;
  return (int) tot;
}

Compilation message (stderr)

circuit.cpp: In function 'void dfs(int, ll)':
circuit.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int j = 0; j < ch[c].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~
circuit.cpp:34:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     spa[j] = val[j] * (j + 1 == ch[c].size() ? 1 : spa[j+1]) % MOD;
      |                        ~~~~~~^~~~~~~~~~~~~~~
circuit.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int i = 0; i < ch[c].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~
circuit.cpp:37:58: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     ll wCh = cw * (i == 0 ? 1 : ppa[i-1]) % MOD * (i + 1 == ch[c].size() ? 1 : spa[i+1]) % MOD;
      |                                                    ~~~~~~^~~~~~~~~~~~~~~

• 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