oj.uz

Submission #1064380

# Submission time Handle Problem Language Result Execution time Memory
1064380 2024-08-18T12:00:56 Z MarwenElarbi Digital Circuit (IOI22_circuit) C++17
0 / 100
 8 ms 2392 KB 
#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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '509', found: '0'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '645927056'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '509', found: '0'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2392 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2392 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '645927056'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '509', found: '0'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '509', found: '0'
4 Halted 0 ms 0 KB -