Submission #866786

#	Time	Username	Problem	Language	Result	Execution time	Memory
866786		Pety	Digital Circuit (IOI22_circuit)	C++17	100 / 100	733 ms	37828 KiB

circuit

  #include <bits/stdc++.h>


  using namespace std;

  const int mod = 1000002022;
  const int N = 1e5+2;
  const int NM = 2e5+2;
  int n, m, val[NM], lazy[4*N], contrib[N];
  vector<int>G[NM];

  pair<int, int>aint[4*N];

  pair<int, int>init_contrib[NM];

  void dfs (int nod) {
    if (nod >= n) {
      val[nod] = 1;
      return;
    }
    val[nod] = G[nod].size();
    for (auto it : G[nod]) {
      dfs(it);
      val[nod] = 1ll * val[it] * val[nod] % mod;
    }
  } 

  void dfs_contrib (int nod, int c) {
    if (nod >= n) {
      contrib[nod - n] = c;
      return;
    }
    vector<int>pref(G[nod].size());
    vector<int>suf(G[nod].size());
    for (int i = 0; i < G[nod].size(); i++) {
      int child = G[nod][i];
      pref[i] = val[child];
      if (i)
        pref[i] = 1ll * pref[i - 1] * pref[i] % mod;
    }
    for (int i = G[nod].size() - 1; i >= 0; i--) {
      int child = G[nod][i];
      suf[i] = val[child];
      if (i + 1 < G[nod].size())
        suf[i] = 1ll * suf[i] * suf[i + 1] % mod;
    }
    for (int i = 0; i < G[nod].size(); i++) {
      int child = G[nod][i];
      int val = c;
      if (i > 0)
        val = 1ll * val * pref[i - 1] % mod;
      if (i + 1 < G[nod].size())
        val = 1ll * val * suf[i + 1] % mod;
      dfs_contrib(child, val);
    }
  }

  pair<int, int> operator+ (pair<int, int> a, pair<int, int>b) {
    return {(a.first + b.first) % mod, (a.second + b.second) % mod};
  }

  void build (int nod, int st, int dr) {
    if (st == dr) {
      aint[nod] = init_contrib[st];
      return;
    }
    int mid = (st + dr) / 2;
    build(2 * nod, st, mid);
    build(2 * nod + 1, mid + 1, dr);
    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
  }

  void push (int nod) {
    if (!lazy[nod])
      return;
    for (int i = 0; i < 2; i++) {
      swap(aint[2 * nod + i].first, aint[2 * nod + i].second);
      lazy[2 * nod + i] ^= 1;
    }
    lazy[nod] = 0;
  }

  void update (int nod, int st, int dr, int a, int b) {
    if (a <= st && dr <= b) {
      swap(aint[nod].first, aint[nod].second);
      lazy[nod] ^= 1;
      return;
    }
    int mid = (st + dr) / 2;
    push(nod);
    if (a <= mid)
      update(2 * nod, st, mid, a, b);
    if (b > mid)
      update(2 * nod + 1, mid + 1, dr, a, b);
    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
  }


  void init (int _n, int _m, vector<int>P, vector<int> A) {
    n = _n;
    m = _m;
    for (int i = 1; i < P.size(); i++)
      G[P[i]].push_back(i);
    dfs(0);
    dfs_contrib(0, 1);
    for (int i = 0; i < m; i++) {
      pair<int, int>c = {0, contrib[i]};
      if (!A[i])
        swap(c.first, c.second);
      init_contrib[i] = c;
    }
    build(1, 0, m - 1);
  }

  int count_ways(int l, int r) {
    update(1, 0, m - 1, l - n, r - n);
    return aint[1].second;
  }

Compilation message (stderr)

circuit.cpp: In function 'void dfs_contrib(int, int)':
circuit.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < G[nod].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
circuit.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |       if (i + 1 < G[nod].size())
      |           ~~~~~~^~~~~~~~~~~~~~~
circuit.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i < G[nod].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
circuit.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |       if (i + 1 < G[nod].size())
      |           ~~~~~~^~~~~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i = 1; i < P.size(); i++)
      |                     ~~^~~~~~~~~~

• 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