Submission #1360531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1360531		altern23	Digital Circuit (IOI22_circuit)	C++20	18 / 100	3015 ms	3900 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], prod[MAXN+5], state[MAXN+5], N, M;

void dfs(ll idx) {
      prod[idx] = 1;

      if (idx >= N) {
            dp[idx] = state[idx];
            return;
      }

      dp[idx] = 0;
      
      for (auto i : adj[idx]) {
            dfs(i);
            dp[idx] *= prod[i]%MOD;
            dp[idx] %= MOD;
            dp[idx] += prod[idx]*dp[i]%MOD;
            dp[idx] %= MOD;
            prod[idx] *= prod[i];
            prod[idx] %= MOD;
      }

      prod[idx] *= (ll)adj[idx].size();
      prod[idx] %= MOD;
}

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];
}

• 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