제출 #1227134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227134		brinton	디지털 회로 (IOI22_circuit)	C++20	18 / 100	3088 ms	3900 KiB

circuit

#include "circuit.h"

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

vector<vector<int>> child;
vector<long long> black,white;
int N,M;
void init(int iN, int iM, vector<int> P, vector<int> A) {
  N = iN,M = iM;
  child.resize(N);
  black.resize(N+M);
  white.resize(N+M);
  for(int i = 1;i < P.size();i++){
    child[P[i]].push_back(i);
  }
  for(int i = 0;i < M;i++){
    if(A[i] == 1){
      //black
      black[N+i] = 1;
    }else{
      // white
      white[N+i] = 1;
    }
  }
}

int count_ways(int L, int R) {
  for(int i = L;i <= R;i++){
    swap(black[i],white[i]);
  }
  for(int i = N-1;i >= 0;i--){
    long long cblack = 0,tot = 1;
    for(auto c:child[i]){
      cblack = (cblack*(white[c]+black[c])+(black[c]*tot))%MOD;
      tot = tot*(white[c]+black[c])%MOD;
    }
    tot *= child[i].size()%MOD;
    black[i] = cblack;
    white[i] = (tot-cblack+MOD)%MOD;
  }
  return black[0];
  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