Submission #1360522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1360522		altern23	Digital Circuit (IOI22_circuit)	C++20	18 / 100	3086 ms	3896 KiB

circuit

#include "circuit.h"

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

#define ll long long

const int MOD = 1'000'002'022;
const int MAXN =  2e5;

vector <int> adj[MAXN+5];
ll dp[MAXN+5][2], state[MAXN+5], N, M;

void dfs(ll idx) {
      if (idx >= N) {
            dp[idx][state[idx]] = 1;
            dp[idx][!state[idx]] = 0;
            return;
      }

      ll prod = 1;

      dp[idx][0] = dp[idx][1] = 0;

      for (auto i : adj[idx]) {
            dfs(i);

            vector <ll> ndp(2);

            ndp[0] += dp[idx][0]*(dp[i][0]+dp[i][1])%MOD;
            ndp[0] += prod*dp[i][0]%MOD;
            ndp[0] %= MOD;

            ndp[1] += dp[idx][1]*(dp[i][0]+dp[i][1])%MOD;
            ndp[1] += prod*dp[i][1]%MOD;
            ndp[1] %= MOD;

            prod *= (dp[i][0]+dp[i][1]);
            prod %= MOD;

            for (int j = 0; j < 2; j++) {
                  dp[idx][j] = ndp[j];
            }
      }
}

void init(int n, int m, vector<int> P, vector<int> A) {
      N = n, M = m;
      for (int i = 1; i < N+M; i++) {
            adj[P[i]].push_back(i);
      }
      for (int i = 0; i < M; i++) {
            state[i+N] = A[i];
      }
}

int count_ways(int L, int R) {
      for (int i = L; i <= R; i++) state[i] ^= 1;
      dfs(0);
      return dp[0][1];
}

• 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