제출 #627715

#제출 시각아이디문제언어결과실행 시간메모리
627715dqhungdl디지털 회로 (IOI22_circuit)C++17
4 / 100
996 ms29640 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; const int MAX = 2e5 + 5, MOD = 1e9 + 2022; int N; long long C[MAX], f[MAX]; vector<int> g[MAX]; struct SegmentTree { int n; vector<vector<long long>> tree; vector<int> lazy; SegmentTree() {} SegmentTree(vector<vector<long long>> &V) { n = V.size(); tree.resize(4 * n + 5, {0, 0}); lazy.resize(4 * n + 5); init(1, 0, n - 1, V); } void init(int k, int l, int r, vector<vector<long long>> &V) { if (l == r) { tree[k] = V[l]; return; } int mid = (l + r) / 2; init(2 * k, l, mid, V); init(2 * k + 1, mid + 1, r, V); for (int i = 0; i <= 1; i++) tree[k][i] = (tree[2 * k][i] + tree[2 * k + 1][i]) % MOD; } void down(int k) { if (lazy[k]) { lazy[2 * k] ^= lazy[k], lazy[2 * k + 1] ^= lazy[k]; if (lazy[2 * k]) swap(tree[2 * k][0], tree[2 * k][1]); if (lazy[2 * k + 1]) swap(tree[2 * k + 1][0], tree[2 * k + 1][1]); lazy[k] = 0; } } void update(int k, int l, int r, int L, int R) { if (l > R || L > r) return; if (L <= l && r <= R) { swap(tree[k][0], tree[k][1]); lazy[k] ^= 1; return; } down(k); int mid = (l + r) / 2; update(2 * k, l, mid, L, R); update(2 * k + 1, mid + 1, r, L, R); for (int i = 0; i <= 1; i++) tree[k][i] = (tree[2 * k][i] + tree[2 * k + 1][i]) % MOD; } void update(int L, int R) { update(1, 0, n - 1, L, R); } } tree; void dfs(int u) { if (g[u].empty()) { C[u] = 1; return; } C[u] = g[u].size(); for (int v: g[u]) { dfs(v); C[u] = C[u] * C[v] % MOD; } vector<long long> L(g[u].size(), 1), R(g[u].size(), 1); for (int i = 1; i < g[u].size(); i++) L[i] = L[i - 1] * C[g[u][i - 1]] % MOD; for (int i = (int) g[u].size() - 2; i >= 0; i--) R[i] = R[i + 1] * C[g[u][i + 1]] % MOD; for (int i = 0; i < g[u].size(); i++) f[g[u][i]] = L[i] * R[i] % MOD; } void init(int _N, int M, vector<int> P, vector<int> A) { N = _N; for (int i = 1; i < N + M; i++) g[P[i]].push_back(i); dfs(0); f[0] = 1; for (int i = 1; i < N + M; i++) f[i] = f[i] * f[P[i]] % MOD; vector<vector<long long>> V(M); for (int i = 0; i < M; i++) if (A[i]) V[i] = {0, f[i + N]}; else V[i] = {f[i + N], 0}; tree = SegmentTree(V); } int count_ways(int L, int R) { tree.update(L - N, R - N); return tree.tree[1][1]; } //int main() { // freopen("../_input", "r", stdin); // int N, M, Q; // assert(3 == scanf("%d %d %d", &N, &M, &Q)); // std::vector<int> P(N + M), A(M); // for (int i = 0; i < N + M; ++i) { // assert(1 == scanf("%d", &P[i])); // } // for (int j = 0; j < M; ++j) { // assert(1 == scanf("%d", &A[j])); // } // init(N, M, P, A); // // for (int i = 0; i < Q; ++i) { // int L, R; // assert(2 == scanf("%d %d", &L, &R)); // printf("%d\n", count_ways(L, R)); // } // return 0; //}

컴파일 시 표준 에러 (stderr) 메시지

circuit.cpp: In function 'void dfs(int)':
circuit.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 1; i < g[u].size(); i++)
      |                     ~~^~~~~~~~~~~~~
circuit.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i = 0; i < g[u].size(); i++)
      |                     ~~^~~~~~~~~~~~~
#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...