Submission #1057304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057304		esomer	Digital Circuit (IOI22_circuit)	C++17	18 / 100	3091 ms	3672 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1000002022;

int n;
vector<vector<int>> Adj;
vector<int> A;

pair<ll, ll> getAns(int x){
  int sz = (int)Adj[x].size();
  if(!sz){
    if(A[x-n]) return {1, 0};
    else return {0, 1};
  }
  vector<ll> ways(sz + 1, 0); ways[0] = 1;
  for(int node : Adj[x]){
    pair<ll, ll> w = getAns(node);
    for(int i = sz; i >= 0; i--){
      if(i+1 <= sz) ways[i+1] = (ways[i+1] + ways[i] * w.first) % MOD;
      ways[i] = (ways[i] * w.second) % MOD;
    }
  }
  // cout << "x " << x << endl;
  // for(int y : ways) cout << y << " ";
  // cout << endl;
  vector<ll> suf(sz+1, 0), pre(sz + 1, 0);
  pre[0] = ways[0];
  for(int i = 1; i <= sz; i++) pre[i] = (pre[i-1] + ways[i]) % MOD;
  suf[sz] = ways[sz];
  for(int i = sz - 1; i >= 0; i--) suf[i] = (suf[i+1] + ways[i]) % MOD;
  ll good = 0, bad = 0;
  for(int c = 1; c <= sz; c++){
    good += suf[c];
    bad += pre[c-1];
    good %= MOD; bad %= MOD;
  }
  // cout << "x " << x << " good " << good << " bad " << bad << "\n";
  return {good, bad};
}

void init(int N, int M, vector<int> P, vector<int> _A) {
  n = N;
  Adj.clear();
  Adj.resize(N+M);
  for(int i = 1; i < N + M; i++){
    Adj[P[i]].push_back(i);
  }
  A = _A;
}

int count_ways(int L, int R) {
  for(int i = L-n; i <= R-n; i++) A[i] ^= 1;
  // for(int i = 0; i < (int)A.size(); i++) cout << A[i] << " ";
  // cout << "\n";
  return (int)(getAns(0).first);
}

// mt19937 gen(time(0));

// int main(){
//   for(int h = 0; h < 10000; h++){    
//     int N = gen() % 5 + 1;
//     int M = gen() % 5 + 1;
//     vector<int> P(N+M);
//     P[0] = -1;
//     for(int i = 1; i < N + M; i++){
//       P[i] = gen() % min(i, N);
//     }
//     vector<int> A(M);
//     for(int i = 0; i < M; i++){
//       A[i] = gen() % 2;
//     }
//     init(N, M, P, A);
//     init2(N, M, P, A);
//     vector<pair<int, int>> queries;
//     int Q = gen() % 10 + 1;
//     bool bad = false;
//     while(Q--){
//       int R = gen() % M + 1;
//       int L = gen() % R + 1;
//       L--; R--; L += N; R += N;
//       queries.push_back({L, R});
//       if(count_ways(L, R) != count_ways2(L, R)){
//         bad = true;
//         break;
//       }
//     }
//     if(bad){
//       cout << N << " " << M << " " << (int)queries.size() << endl;
//       for(int x : P) cout << x << " "; cout << endl;
//       for(int x : A) cout << x << " "; cout << endl;
//       for(pair<int, int> p : queries) cout << p.first << " " << p.second << endl;
//       return 0;
//     }
//   }
// }

• 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: 0 / 28
• Subtask 8: 0 / 11