oj.uz

답안 #1034303

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1034303 2024-07-25T11:59:11 Z Mr_Husanboy 디지털 회로 (IOI22_circuit) C++17
16 / 100
 898 ms 9044 KB 
#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long
const int mod = 1000002022;

vector<int> state, p;
int n, m; 
vector<vector<int>> g;
template<typename T>
int len(T &a){return a.size();}


vector<array<ll, 2>> dp;
vector<int> marked;

void build(int i){
  if(i >= n){
    dp[i][0] = state[i - n] ^ 1;
    dp[i][1] = state[i - n];
    return;
  }
  for(auto u : g[i]) build(u);
  vector<ll> prep(len(g[i]) + 1);
  prep[0] = 1;
  ll al = len(g[i]);
  int cur = 0;
  for(auto u : g[i]){
    cur ++;
    al = al * (dp[u][0] + dp[u][1]) % mod;
    for(int j = cur; j >= 0; j --){
      prep[j] = prep[j] * dp[u][0] % mod;
      if(j) prep[j] += prep[j - 1] * dp[u][1] % mod;
    }
  }
  dp[i][1] = 0;
  for(int j = 1; j <= len(g[i]); j ++){
    dp[i][1] = (dp[i][1] + prep[j] * j) % mod;
  }

  dp[i][0] = al - dp[i][1];
  if(dp[i][0] < 0) dp[i][0] += mod;
}

void push(int i){
  if(!marked[i]) return;
  marked[i] ^= 1;
  int l = g[i][0], r = g[i][1];
  swap(dp[l][0], dp[l][1]);
  swap(dp[r][0], dp[r][1]);
  marked[l] ^= 1;
  marked[r] ^= 1;
}

void upd(int i, int l, int r, int ql, int qr){
  if(l > qr || ql > r) return;
  if(ql <= l && r <= qr){
    swap(dp[i][0], dp[i][1]);
    marked[i] ^= 1;
    return;
  }
  push(i);
  int m = (l + r) / 2;
  upd(g[i][0], l, m, ql, qr);
  upd(g[i][1], m + 1, r, ql, qr);
  vector<ll> prep(len(g[i]) + 1);
  prep[0] = 1;
  ll al = len(g[i]);
  int cur = 0;
  for(auto u : g[i]){
    cur ++;
    al = al * (dp[u][0] + dp[u][1]) % mod;
    for(int j = cur; j >= 0; j --){
      prep[j] = prep[j] * dp[u][0] % mod;
      if(j) prep[j] += prep[j - 1] * dp[u][1] % mod;
    }
  }
  dp[i][1] = 0;
  for(int j = 1; j <= len(g[i]); j ++){
    dp[i][1] = (dp[i][1] + prep[j] * j) % mod;
  }

  dp[i][0] = al - dp[i][1];
  if(dp[i][0] < 0) dp[i][0] += mod;
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
  n = N, m = M;
  g.resize(n);
  state = A;
  p = P;
  for(int i = 1; i < n + m; i ++){
    g[p[i]].push_back(i);
  }
  dp.resize(n + m);
  marked.resize(n + m);
  build(0);

}


int count_ways(int l, int r){
  upd(0, n, n + m - 1, l, r);
  return dp[0][1];
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 2 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Runtime error 1 ms 600 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 2 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 460 ms 4696 KB Output is correct
2 Correct 746 ms 8792 KB Output is correct
3 Correct 743 ms 8792 KB Output is correct
4 Correct 692 ms 9044 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 460 ms 4696 KB Output is correct
2 Correct 746 ms 8792 KB Output is correct
3 Correct 743 ms 8792 KB Output is correct
4 Correct 692 ms 9044 KB Output is correct
5 Correct 649 ms 4676 KB Output is correct
6 Correct 865 ms 8792 KB Output is correct
7 Correct 898 ms 8792 KB Output is correct
8 Correct 784 ms 8792 KB Output is correct
9 Correct 359 ms 852 KB Output is correct
10 Correct 702 ms 856 KB Output is correct
11 Correct 760 ms 856 KB Output is correct
12 Correct 682 ms 856 KB Output is correct

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Runtime error 1 ms 600 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 2 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 2 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -