oj.uz

Submission #798024

# Submission time Handle Problem Language Result Execution time Memory
798024 2023-07-30T09:41:59 Z gesgha Digital Circuit (IOI22_circuit) C++17
61 / 100
 3000 ms 28968 KB 
#include "circuit.h"
#include <bits/stdc++.h>
 
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define fe(x, y) for (auto& x : y)
 
#define fi first
#define se second
#define pb push_back
 
#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
#define sz(x) (int)x.size()
 
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T>
using ve = vector <T>;
 
template <typename T>
bool umx (T& a, T b) { return a < b ? a = b, 1 : 0; }
 
template <typename T>
bool umn (T& a, T b) { return a > b ? a = b, 1 : 0; }
 
using ll = long long;
using ld = long double;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
using ull = unsigned long long;
 
const int oo = 1e9;
const ll OO = 1e18;
const int N = 2e5 + 10;
const int M = 5e3 + 100;
const int mod = 1e9 + 2022;

int a[N];
int dp[N][2];
int dp1[N][2];
ve <int> G[N];
bool ok = 1;


int n, m;

int add(int a, int b) {
  return a + b < mod ? a + b : a + b - mod;
}

int sub(int a, int b) {
  return a - b >= 0 ? a - b : a - b + mod;
}

int mul (int a, int b) {
  return 1LL * a * b % mod;
}
int bpow(int a, int n) {
  int res = 1;
  for (; n; n >>= 1, a = mul(a, a)) if(n&1) res = mul(res, a);
  return res;
}
int tin[N];
int tout[N];
int tim;
int mn[N];
int mx[N];
bool isupper(int u, int v) {
  return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int dead[N];

int S[4 * N];
int res[4 * N];
void build(int v, int tl, int tr) {
  if (tl == tr) {
    S[v] = bpow(2, n - dead[tl + n]);
    if (a[tl + n]) res[v] = bpow(2, n - dead[tl + n]);
    // cout << tl << " - " << res[v] << "\n";
    return;
  }
  int tm = (tl + tr) >> 1;
  build(v << 1, tl, tm);
  build(v << 1 | 1, tm + 1, tr);
  S[v] = add(S[v << 1], S[v << 1 | 1]);
  res[v] = add(res[v << 1], res[v << 1 | 1]);
}

int rev[N * 4];

void push(int v) {
  if (!rev[v]) return;
  for (auto to : {(v << 1), (v << 1 | 1)}) {
    rev[to] ^= 1;
    res[to] = sub(S[to], res[to]);
  }
  rev[v] = 0;
}

void upd(int v, int tl, int tr, int L, int R) {
  // cout << tl << " " << tr << " " << L << " " << R << "\n";
  if (L > R) return;
  if (tl == L && tr == R) {
    res[v] = sub(S[v], res[v]);
    rev[v] ^= 1;
    return;
  }
  int tm = (tl + tr) >> 1;
  push(v);
  upd(v << 1, tl, tm, L, min(R, tm));
  upd(v << 1 | 1, tm + 1, tr, max(L, tm + 1), R);
  res[v] = add(res[v << 1], res[v << 1 | 1]);
}

void dfs(int u) {
  tin[u] = tim++;
  if (!sz(G[u])) {
    mn[u] = u;
    mx[u] = u;
    if(a[u]) {
      dp[u][0] = 0;
      dp[u][1] = 1;
    } else {
      dp[u][0] = 1;
      dp[u][1] = 0;
    }
    return;
  }
  mx[u] = -oo;
  mn[u] = oo;
  for (auto to : G[u]) {
    dead[to] = dead[u] + 1;
    dfs(to);
    mx[u] = max(mx[u], mx[to]);
    mn[u] = min(mn[u], mn[to]);
  }
  ve <ve <int>> d(sz(G[u]) + 1);

  fe (x, d) x.resize(sz(G[u]) + 1);
  d[0][0] = 1;
  for (int i = 0; i < sz(G[u]); i++) {
    int to = G[u][i];
    for (int cnt_al = 0; cnt_al <= i; cnt_al++) {
      d[i + 1][cnt_al + 1] = add(d[i + 1][cnt_al + 1], mul(d[i][cnt_al], dp[to][1]));
      d[i + 1][cnt_al] = add(d[i + 1][cnt_al], mul(d[i][cnt_al], dp[to][0]));
    }
  }
  dp[u][0] = dp[u][1] = 0;
  for (int cnt_al = 0; cnt_al <= sz(G[u]); cnt_al++) {
    dp[u][1] = add(dp[u][1], mul(d[sz(G[u])][cnt_al], max(0, cnt_al)));
    dp[u][0] = add(dp[u][0], mul(d[sz(G[u])][cnt_al], sz(G[u]) - cnt_al));
  }
  tout[u] = tim;
}




void init(int N, int M, vector<int> P, vector<int> A) {
  n = N;
  m = M;
  for (int i = 0; i < M; i++) a[i + N] = A[i];
  for (int i = 1; i < N + M; i++) G[P[i]].pb(i);
  for (int i = 0; i < N; i++) ok &= bool(sz(G[i]) == 2);
  dfs(0);

  if (ok) {
      build(1, 0, m - 1);
  }
}

int count_ways(int L, int R) {

  if (!ok) {
    for (int i = L; i <= R; i++) {
      a[i] = 1 - a[i];
    }
    dfs(0);
  } else {
    L -= n;
    R -= n;
    upd(1, 0, m - 1, L, R);
    return res[1];
  }
  
  return dp[0][1];
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 20 ms 8828 KB Output is correct
4 Correct 21 ms 9040 KB Output is correct
5 Correct 21 ms 9028 KB Output is correct
6 Correct 21 ms 9040 KB Output is correct
7 Correct 21 ms 9048 KB Output is correct
8 Correct 21 ms 9040 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 5072 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 3 ms 5072 KB Output is correct
10 Correct 3 ms 5200 KB Output is correct
11 Correct 4 ms 5224 KB Output is correct
12 Correct 3 ms 5072 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 20 ms 8828 KB Output is correct
4 Correct 21 ms 9040 KB Output is correct
5 Correct 21 ms 9028 KB Output is correct
6 Correct 21 ms 9040 KB Output is correct
7 Correct 21 ms 9048 KB Output is correct
8 Correct 21 ms 9040 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 5072 KB Output is correct
11 Correct 4 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Correct 3 ms 5072 KB Output is correct
15 Correct 3 ms 5072 KB Output is correct
16 Correct 3 ms 5072 KB Output is correct
17 Correct 3 ms 5072 KB Output is correct
18 Correct 3 ms 5200 KB Output is correct
19 Correct 4 ms 5224 KB Output is correct
20 Correct 3 ms 5072 KB Output is correct
21 Correct 4 ms 5072 KB Output is correct
22 Correct 3 ms 5072 KB Output is correct
23 Correct 3 ms 5072 KB Output is correct
24 Correct 3 ms 5072 KB Output is correct
25 Correct 4 ms 5072 KB Output is correct
26 Correct 3 ms 5072 KB Output is correct
27 Correct 4 ms 5072 KB Output is correct
28 Correct 3 ms 5072 KB Output is correct
29 Correct 21 ms 9096 KB Output is correct
30 Correct 21 ms 9040 KB Output is correct
31 Correct 3 ms 5200 KB Output is correct
32 Correct 3 ms 5196 KB Output is correct
33 Correct 3 ms 5072 KB Output is correct
34 Correct 3 ms 5072 KB Output is correct
35 Correct 6 ms 5272 KB Output is correct
36 Correct 3 ms 5200 KB Output is correct
37 Correct 21 ms 9240 KB Output is correct
38 Correct 22 ms 9216 KB Output is correct
39 Correct 3 ms 5072 KB Output is correct
40 Correct 3 ms 5072 KB Output is correct
41 Correct 3 ms 5072 KB Output is correct
42 Correct 3 ms 5072 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 9072 KB Output is correct
2 Correct 643 ms 13312 KB Output is correct
3 Correct 712 ms 13208 KB Output is correct
4 Correct 714 ms 13000 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 9072 KB Output is correct
2 Correct 643 ms 13312 KB Output is correct
3 Correct 712 ms 13208 KB Output is correct
4 Correct 714 ms 13000 KB Output is correct
5 Correct 661 ms 9160 KB Output is correct
6 Correct 670 ms 13208 KB Output is correct
7 Correct 628 ms 13204 KB Output is correct
8 Correct 752 ms 13244 KB Output is correct
9 Correct 402 ms 5336 KB Output is correct
10 Correct 681 ms 5584 KB Output is correct
11 Correct 751 ms 5584 KB Output is correct
12 Correct 747 ms 5584 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 5072 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 3 ms 5072 KB Output is correct
10 Correct 3 ms 5200 KB Output is correct
11 Correct 4 ms 5224 KB Output is correct
12 Correct 3 ms 5072 KB Output is correct
13 Correct 358 ms 9072 KB Output is correct
14 Correct 643 ms 13312 KB Output is correct
15 Correct 712 ms 13208 KB Output is correct
16 Correct 714 ms 13000 KB Output is correct
17 Correct 661 ms 9160 KB Output is correct
18 Correct 670 ms 13208 KB Output is correct
19 Correct 628 ms 13204 KB Output is correct
20 Correct 752 ms 13244 KB Output is correct
21 Correct 402 ms 5336 KB Output is correct
22 Correct 681 ms 5584 KB Output is correct
23 Correct 751 ms 5584 KB Output is correct
24 Correct 747 ms 5584 KB Output is correct
25 Correct 772 ms 17792 KB Output is correct
26 Correct 832 ms 18020 KB Output is correct
27 Correct 723 ms 17992 KB Output is correct
28 Correct 595 ms 17924 KB Output is correct
29 Correct 701 ms 28968 KB Output is correct
30 Correct 810 ms 28960 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 20 ms 8828 KB Output is correct
4 Correct 21 ms 9040 KB Output is correct
5 Correct 21 ms 9028 KB Output is correct
6 Correct 21 ms 9040 KB Output is correct
7 Correct 21 ms 9048 KB Output is correct
8 Correct 21 ms 9040 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 5072 KB Output is correct
11 Correct 4 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Correct 3 ms 5072 KB Output is correct
15 Correct 3 ms 5072 KB Output is correct
16 Correct 3 ms 5072 KB Output is correct
17 Correct 3 ms 5072 KB Output is correct
18 Correct 3 ms 5200 KB Output is correct
19 Correct 4 ms 5224 KB Output is correct
20 Correct 3 ms 5072 KB Output is correct
21 Correct 4 ms 5072 KB Output is correct
22 Correct 3 ms 5072 KB Output is correct
23 Correct 3 ms 5072 KB Output is correct
24 Correct 3 ms 5072 KB Output is correct
25 Correct 4 ms 5072 KB Output is correct
26 Correct 3 ms 5072 KB Output is correct
27 Correct 4 ms 5072 KB Output is correct
28 Correct 3 ms 5072 KB Output is correct
29 Correct 21 ms 9096 KB Output is correct
30 Correct 21 ms 9040 KB Output is correct
31 Correct 3 ms 5200 KB Output is correct
32 Correct 3 ms 5196 KB Output is correct
33 Correct 3 ms 5072 KB Output is correct
34 Correct 3 ms 5072 KB Output is correct
35 Correct 6 ms 5272 KB Output is correct
36 Correct 3 ms 5200 KB Output is correct
37 Correct 21 ms 9240 KB Output is correct
38 Correct 22 ms 9216 KB Output is correct
39 Correct 3 ms 5072 KB Output is correct
40 Correct 3 ms 5072 KB Output is correct
41 Correct 3 ms 5072 KB Output is correct
42 Correct 3 ms 5072 KB Output is correct
43 Execution timed out 3050 ms 5328 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 20 ms 8828 KB Output is correct
4 Correct 21 ms 9040 KB Output is correct
5 Correct 21 ms 9028 KB Output is correct
6 Correct 21 ms 9040 KB Output is correct
7 Correct 21 ms 9048 KB Output is correct
8 Correct 21 ms 9040 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 5072 KB Output is correct
11 Correct 4 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Correct 3 ms 5072 KB Output is correct
15 Correct 3 ms 5072 KB Output is correct
16 Correct 3 ms 5072 KB Output is correct
17 Correct 3 ms 5072 KB Output is correct
18 Correct 3 ms 5200 KB Output is correct
19 Correct 4 ms 5224 KB Output is correct
20 Correct 3 ms 5072 KB Output is correct
21 Correct 4 ms 5072 KB Output is correct
22 Correct 3 ms 5072 KB Output is correct
23 Correct 3 ms 5072 KB Output is correct
24 Correct 3 ms 5072 KB Output is correct
25 Correct 4 ms 5072 KB Output is correct
26 Correct 3 ms 5072 KB Output is correct
27 Correct 4 ms 5072 KB Output is correct
28 Correct 3 ms 5072 KB Output is correct
29 Correct 21 ms 9096 KB Output is correct
30 Correct 21 ms 9040 KB Output is correct
31 Correct 3 ms 5200 KB Output is correct
32 Correct 3 ms 5196 KB Output is correct
33 Correct 3 ms 5072 KB Output is correct
34 Correct 3 ms 5072 KB Output is correct
35 Correct 6 ms 5272 KB Output is correct
36 Correct 3 ms 5200 KB Output is correct
37 Correct 21 ms 9240 KB Output is correct
38 Correct 22 ms 9216 KB Output is correct
39 Correct 3 ms 5072 KB Output is correct
40 Correct 3 ms 5072 KB Output is correct
41 Correct 3 ms 5072 KB Output is correct
42 Correct 3 ms 5072 KB Output is correct
43 Correct 358 ms 9072 KB Output is correct
44 Correct 643 ms 13312 KB Output is correct
45 Correct 712 ms 13208 KB Output is correct
46 Correct 714 ms 13000 KB Output is correct
47 Correct 661 ms 9160 KB Output is correct
48 Correct 670 ms 13208 KB Output is correct
49 Correct 628 ms 13204 KB Output is correct
50 Correct 752 ms 13244 KB Output is correct
51 Correct 402 ms 5336 KB Output is correct
52 Correct 681 ms 5584 KB Output is correct
53 Correct 751 ms 5584 KB Output is correct
54 Correct 747 ms 5584 KB Output is correct
55 Correct 772 ms 17792 KB Output is correct
56 Correct 832 ms 18020 KB Output is correct
57 Correct 723 ms 17992 KB Output is correct
58 Correct 595 ms 17924 KB Output is correct
59 Correct 701 ms 28968 KB Output is correct
60 Correct 810 ms 28960 KB Output is correct
61 Execution timed out 3050 ms 5328 KB Time limit exceeded
62 Halted 0 ms 0 KB -