oj.uz

답안 #1057355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1057355 2024-08-13T17:52:41 Z spacewalker 디지털 회로 (IOI22_circuit) C++17
4 / 100
 580 ms 17356 KB 
#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr ll MOD = 1'000'002'022;

template<class T>
ostream& operator<< (ostream &os, const vector<T> &arr) {
  os << "[";
  for (const T &v : arr) os << v << ", ";
  return os << "]";
}

vector<ll> product_except(vector<ll> nums) {
  int n = nums.size();
  vector<ll> pref = nums, suff = nums;
  for (int i = 1; i < n; ++i) pref[i] = (pref[i-1] * nums[i]) % MOD;
  for (int i = n - 2; i >= 0; --i) suff[i] = suff[i+1] * nums[i] % MOD;
  vector<ll> ans(n);
  for (int i = 0; i < n; ++i) ans[i] = (i > 0 ? pref[i-1] : 1) * (i + 1 < n ? suff[i+1] : 1) % MOD;
  return ans;
}

vector<ll> get_weights(vector<int> P, int M) {
  int N = (int)P.size() - M;
  vector<vector<int>> children(N + M);
  for (int i = 1; i < N + M; ++i) children[P[i]].push_back(i);
  vector<ll> assign_ways(N + M, 1);
  for (int i = N - 1; i >= 0; --i) {
    assign_ways[i] = children[i].size();
    for (int ch : children[i]) assign_ways[i] = (assign_ways[i] * assign_ways[ch]) % MOD;
  }
  vector<ll> ans(N + M, 1);
  for (int i = 0; i < N; ++i) {
    vector<ll> ways_children(children[i].size());
    for (int j = 0; j < children[i].size(); ++j) ways_children[j] = assign_ways[children[i][j]];
    vector<ll> ways_except = product_except(ways_children);
    for (int j = 0; j < children[i].size(); ++j) ans[children[i][j]] = (ans[children[i][j]] * ways_except[j] % MOD * ans[i]) % MOD;
  }
  return vector(begin(ans) + N, end(ans));
}

struct CircuitTree {
  ll total, totalFlip;
  int wt, al, ar;
  bool lazy;
  unique_ptr<CircuitTree> left, right;
  void combine() {
    total = (left->total + right->total) % MOD;
    totalFlip = (left->totalFlip + right->totalFlip) % MOD;
  }
 void propagate() {
    if (lazy) {
      swap(total, totalFlip);
      if (left) left->lazy = right->lazy = true;
      lazy = false;
    }
  }
  CircuitTree() {}
  CircuitTree(int i, int j, const vector<ll> &weights, const vector<int> &init) : total(0), totalFlip(0), al(i), ar(j), lazy(false) {
    if (i == j) {
      wt = totalFlip = weights[i];
      if (init[i]) swap(total, totalFlip);
    } else {
      int k = (i + j) / 2;
      left = make_unique<CircuitTree>(i, k, weights, init);
      right = make_unique<CircuitTree>(k + 1, j, weights, init);
      combine();
      // cerr << "[" << i << ", " << j << "] total " << total << " " << totalFlip << endl;
    }
  }
  void flip(int i, int j) {
    propagate();
    if (j < al || ar < i) return;
    if (i <= al && ar <= j) {
      lazy = true; propagate();
    } else {
      left->flip(i, j); right->flip(i, j);
      combine();
    }
  }
  ll sum() {
    propagate();
    return total;
  }
};

struct DumbCircuitTree {
  vector<int> p, a;
  int n, m;
  vector<vector<int>> children;
  DumbCircuitTree() {}
  DumbCircuitTree(vector<int> p, vector<int> a) : p(p), a(a), n((int)p.size() - (int)a.size()), m(a.size()), children(n + m) {
    for (int i = n + m - 1; i > 0; --i) children[p[i]].push_back(i);
  }
  void flip(int L, int R) {
    for (int j = L; j <= R; ++j) a[j] = 1 - a[j];
  }
  bool check_state(vector<int> &thresholds) {
    vector<int> st(n + m);
    for (int i = 0; i < m; ++i) st[i+n] = a[i];
    for (int i = n-1; i >= 0; --i) {
      int active = 0;
      for (int ch : children[i]) if (st[ch] == 1) ++active;
      if (active >= thresholds[i]) st[i] = 1;
    }
    // cerr << thresholds << " " << st << endl;
    return st[0] == 1;
  }
  int _count_ways(vector<int> &thresholds, int i) {
    if (i == n) return check_state(thresholds) ? 1 : 0;
    else {
      int ans = 0;
      for (int ct = 1; ct <= children[i].size(); ++ct) {
        thresholds[i] = ct;
        ans += _count_ways(thresholds, i + 1);
      }
      return ans;
    }
  }
  int count_ways() {
    // cerr << "got ct " << endl;
    vector<int> thresholds(n, 1);
    return _count_ways(thresholds, 0);
  }
};

CircuitTree ct;
DumbCircuitTree dct;
int N;

void init(int _N, int M, std::vector<int> P, std::vector<int> A) {
  N = _N;
  vector<ll> weights = get_weights(P, M); 
  ct = CircuitTree(0, M - 1, weights, A);
  dct = DumbCircuitTree(P, A);
}

int count_ways(int L, int R) {
  ct.flip(L - N, R - N);
  // dct.flip(L - N, R - N);
  return ct.sum();
  // assert(ct.sum() == dct.count_ways());
  // return dct.count_ways();
}

Compilation message

circuit.cpp: In function 'std::vector<long long int> get_weights(std::vector<int>, int)':
circuit.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int j = 0; j < children[i].size(); ++j) ways_children[j] = assign_ways[children[i][j]];
      |                     ~~^~~~~~~~~~~~~~~~~~~~
circuit.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int j = 0; j < children[i].size(); ++j) ans[children[i][j]] = (ans[children[i][j]] * ways_except[j] % MOD * ans[i]) % MOD;
      |                     ~~^~~~~~~~~~~~~~~~~~~~
circuit.cpp: In member function 'int DumbCircuitTree::_count_ways(std::vector<int>&, int)':
circuit.cpp:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |       for (int ct = 1; ct <= children[i].size(); ++ct) {
      |                        ~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 379 ms 8780 KB Output is correct
2 Correct 553 ms 17356 KB Output is correct
3 Correct 580 ms 17228 KB Output is correct
4 Correct 535 ms 17228 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 379 ms 8780 KB Output is correct
2 Correct 553 ms 17356 KB Output is correct
3 Correct 580 ms 17228 KB Output is correct
4 Correct 535 ms 17228 KB Output is correct
5 Incorrect 485 ms 8780 KB 3rd lines differ - on the 1st token, expected: '249436868', found: '812217068'
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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