Submission #1312452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312452		kawhiet	Digital Circuit (IOI22_circuit)	C++20	0 / 100	209 ms	5760 KiB

circuit

#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;

constexpr int N = 2e5 + 5;
constexpr int mod = 1000002022;

vector<int> a, lvl;
vector<long long> dp;
vector<vector<int>> g;

int m;

void op(int i, int x, int y) {
  int all = (1LL << lvl[i]) % mod;
  dp[i] = 2 * dp[x] * dp[y] % mod + (all - dp[x]) * dp[y] % mod + (all - dp[y]) * dp[x] % mod;
  dp[i] %= mod;
}

void init(int n, int _m, vector<int> p, vector<int> c) {
  m = _m;
  a.resize(n + m);
  g.resize(n + m);
  dp.resize(n + m);
  lvl.resize(n + m);
  for (int i = 1; i < n + m; i++) {
    g[i].push_back(p[i]);
    g[p[i]].push_back(i);
  }
  for (int i = 0; i < m; i++) {
    a[i + n] = c[i];
    dp[i + n] = c[i];
  }
  for (int i = n - 1; i >= 0; i--) {
    lvl[i] = lvl[2 * i + 1] + 1;
  }
  for (int i = n - 1; i >= 0; i--) {
    int x = i * 2 + 1, y = i * 2 + 2;
    op(i, x, y);
  }
}

int count_ways(int l, int r) {
  assert(l == r);
  int i = l;
  dp[i] ^= 1;
  while (i > 0) {
    int p = (i - 1) / 2;
    int x = 2 * p + 1, y = x + 1;
    op(p, x, y);
    i = p;
  }
  return dp[0];
}

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