Submission #630159

#	Time	Username	Problem	Language	Result	Execution time	Memory
630159		CyanForces	Digital Circuit (IOI22_circuit)	C++17	46 / 100	3078 ms	8220 KiB

circuit

#include "circuit.h"

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define debug(...) //ignore
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long double ld;

vi a;
int n,m;
vector<ll> contrib;
const ll mod = ll(1e9) + 2022;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
  n = N, m = M;
  contrib.assign(m,0);
  a = A;

  vector<vi> g(n+m);
  rep(i,1,n+m) g[P[i]].emplace_back(i);



  vector<ll> ways(n);

  function<void(int,int)> dfs = [&](int x, int p) {
    ways[x] = sz(g[x]);
    for(int y : g[x]) if(y != p && y < n) {
      dfs(y,x);
      ways[x] = ways[x] * ways[y] % mod;
    }
  };
  dfs(0,-1);


  function<void(int,int,ll)> go = [&](int x, int p, ll prod) {
    if(x >= n) {
      contrib[x-n] = prod;
      return;
    }
    vector<ll> c;
    for(int y : g[x]) if(y != p && y < n) {
      c.emplace_back(ways[y]);
    }
    vector<ll> pref(sz(c)+1,1), suf(sz(c)+1,1);
    rep(i,0,sz(c)) pref[i+1] = pref[i] * c[i] % mod;
    rep(i,0,sz(c)) suf[i+1] = suf[i] * c[sz(c)-i-1] % mod;
    int before = 0, after = sz(c);
    for(int y : g[x]) if(y != p) {
      if(y < n) --after;
      ll q = pref[before] * suf[after] % mod;
      go(y, x, q * prod % mod);
      if(y < n) ++before;
    }
    assert(after == 0 && before == sz(c));
  };
  go(0,-1,1);
}

int count_ways(int L, int R) {
  int l = L - n;
  int r = R - n;
  rep(i,l,r+1) a[i] = 1-a[i];
  ll ans = 0;
  rep(i,0,m) ans += contrib[i]*a[i];
  return int(ans % mod);
}

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