제출 #1064380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1064380		MarwenElarbi	Digital Circuit (IOI22_circuit)	C++17	0 / 100	8 ms	2392 KiB

circuit

#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
#define pb push_back
#define ll long long
#define fi first
#define se second
const int nax=2e3+5;
const int MOD=1e9+2022;
vector<int> adj[nax];
long long dp[nax][2];
int tab[nax];
int on[nax];
int sz[nax];
long long pw[nax];
int n,m;
void precompute(int x){
  if(x>=n){
    return;
  }
  sz[x]=1;
  for(auto u:adj[x]){
    if(u>=n&&tab[u-n]) on[x]++;
    else if(u>=n) continue;
    else{
      precompute(u);
      sz[x]+=sz[u];
    }
  }
  return;
}
long long dfs(int x,int c){
  if(dp[x][c]!=-1) return dp[x][c];
  dp[x][c]=0;
  if(on[x]==2) return dp[x][c]=1;
  else if(on[x]==1){
    if(c==0){
      return dp[x][c]=pw[sz[x]-1];
    }else if(sz[x]==1){
      return dp[x][c]=0;
    }
    for(auto u:adj[x]){
      if(u>=n) continue;
      dfs(u,0);
      dfs(u,1);
      return dp[x][c]=(dp[u][0]+dp[u][1])%MOD;
    }
  }else{
    vector<long long> cur;
    for(auto u:adj[x]){
      if(u>=n){
        cur.pb(0);
        continue;
      }
      dfs(u,0);
      dfs(u,1);
      cur.pb(dp[u][0]+dp[u][1]);
    }
    if(cur[0]==0||cur[1]==0){
      if(c==0) return dp[x][c]=(cur[0]+cur[1])%MOD;
      else return dp[x][c]=0;
    }else{
      return dp[x][c]=(cur[0]%MOD)*(cur[1]%MOD)%MOD;
    }
  }
}
void init(int N, int M, std::vector<int> P, std::vector<int> A){
  n=N;m=M;
  memset(dp,-1,sizeof dp);
  pw[0]=1;
  for(int i=1;i<nax;i++) pw[i]=(pw[i-1]*2)%MOD;
  for (int i = 1; i < N+M; ++i)
  {
    adj[P[i]].pb(i);
  }
  for (int i = 0; i < M; ++i)
  {
    tab[i]=A[i];
  }
  return;
}
 
int count_ways(int L, int R) {
  for (int i = L-n; i <= R-n; ++i)
  {
    tab[i]^=1;
  }
  memset(on,0,sizeof on);
  precompute(0);
  memset(dp,-1,sizeof dp);
  dfs(0,0);
  dfs(0,1);
  return (dp[0][0]+dp[0][1])%MOD;
}

컴파일 시 표준 에러 (stderr) 메시지

circuit.cpp: In function 'long long int dfs(int, int)':
circuit.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^

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