제출 #1051171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1051171		Trent	디지털 회로 (IOI22_circuit)	C++17	62 / 100	676 ms	37584 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;
  for(int i : ch[c]) {
    ll wCh = cw;
    for(int j : ch[c]) if(j != i) wCh = wCh * totPos[j] % MOD;
    dfs(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(2 * c + 1 < ME) {
    if(seg[c].lz) {
      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;
}

• 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