제출 #1079020

#제출 시각아이디문제언어결과실행 시간메모리
1079020Boas디지털 회로 (IOI22_circuit)C++17
18 / 100
3070 ms2988 KiB
#include "circuit.h" #pragma GCC optimize("trapv") #include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define loop(x, i) for (int i = 0; i < x; i++) #define rev(x, i) for (int i = (int)x - 1; i >= 0; i--) #define ALL(x) begin(x), end(x) #define sz(x) (int)x.size() typedef signed i32; typedef array<int, 2> ii; typedef vector<ii> vii; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<i32> vi32; typedef vector<vi> vvi; constexpr int MOD = 1'000'002'022; vvi children; int n, m; vb a; void init(i32 N, i32 M, vi32 P, vi32 A) { n = N; m = M; children = vvi(N); a = vb(M); loop(sz(P), i) { if (i == 0) continue; children[P[i]].pb(i); } loop(sz(A), i) { a[i] = A[i]; } } ii calc(int i) { if (i >= n) { if (a[i - n]) return {1, 1}; return {1, 0}; } int all = sz(children[i]), r1 = 0; vi alls, ones; vi prefProd; vi sufProd; for (int j : children[i]) { auto [allJ, v1] = calc(j); all *= allJ; all %= MOD; alls.pb(allJ); ones.pb(v1); } loop(sz(children[i]), j) { int allExcept = 1; loop(sz(children[i]), k) { if (j == k) continue; allExcept *= alls[k]; allExcept %= MOD; } r1 += allExcept * ones[j]; r1 %= MOD; } if (sz(children[i]) == 2) { assert(all == (2 * alls[0] * alls[1]) % MOD); assert(r1 == (alls[0] * ones[1] + ones[0] * alls[1]) % MOD); } return {all % MOD, r1 % MOD}; } i32 count_ways(i32 L, i32 R) { for (int i = L; i <= R; i++) { a[i - n].flip(); } return calc(0)[1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...