oj.uz

답안 #798022

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
798022 2023-07-30T09:38:42 Z gesgha 디지털 회로 (IOI22_circuit) C++17
50 / 100
 912 ms 28960 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;
  }
  ok &= (sz(G[u]) == 2);
  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);
  dfs(0);

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

int count_ways(int L, int R) {

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

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 5072 KB Output is correct
3 Correct 3 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 2 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 3 ms 5200 KB Output is correct
12 Correct 3 ms 5072 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 548 ms 9064 KB Output is correct
2 Correct 541 ms 13256 KB Output is correct
3 Correct 671 ms 13212 KB Output is correct
4 Correct 740 ms 12928 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 548 ms 9064 KB Output is correct
2 Correct 541 ms 13256 KB Output is correct
3 Correct 671 ms 13212 KB Output is correct
4 Correct 740 ms 12928 KB Output is correct
5 Correct 622 ms 9132 KB Output is correct
6 Correct 732 ms 13256 KB Output is correct
7 Correct 755 ms 13256 KB Output is correct
8 Correct 576 ms 13260 KB Output is correct
9 Correct 391 ms 5328 KB Output is correct
10 Correct 757 ms 5584 KB Output is correct
11 Correct 712 ms 5584 KB Output is correct
12 Correct 721 ms 5584 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 5072 KB Output is correct
3 Correct 3 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 2 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 3 ms 5200 KB Output is correct
12 Correct 3 ms 5072 KB Output is correct
13 Correct 548 ms 9064 KB Output is correct
14 Correct 541 ms 13256 KB Output is correct
15 Correct 671 ms 13212 KB Output is correct
16 Correct 740 ms 12928 KB Output is correct
17 Correct 622 ms 9132 KB Output is correct
18 Correct 732 ms 13256 KB Output is correct
19 Correct 755 ms 13256 KB Output is correct
20 Correct 576 ms 13260 KB Output is correct
21 Correct 391 ms 5328 KB Output is correct
22 Correct 757 ms 5584 KB Output is correct
23 Correct 712 ms 5584 KB Output is correct
24 Correct 721 ms 5584 KB Output is correct
25 Correct 819 ms 17792 KB Output is correct
26 Correct 802 ms 17924 KB Output is correct
27 Correct 866 ms 17956 KB Output is correct
28 Correct 714 ms 17932 KB Output is correct
29 Correct 722 ms 28872 KB Output is correct
30 Correct 912 ms 28960 KB Output is correct

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -