제출 #1079167

#제출 시각아이디문제언어결과실행 시간메모리
1079167Boas디지털 회로 (IOI22_circuit)C++17
62 / 100
3029 ms47420 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<vii> vvii; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<i32> vi32; typedef vector<vi> vvi; typedef vector<vvi> vvvi; constexpr int MOD = 1'000'002'022; vvi children; vi term01; int n, m, treeN = 1; vi vs; struct val { int v = 0, totalV = 0; void swap() { v = (totalV - v + MOD) % MOD; } val operator+(const val &b) { val a = *this, res; res.v = a.v + b.v; res.totalV = a.totalV + b.totalV; res.totalV %= MOD; res.v %= MOD; return res; } }; vector<val> tree; vb lazy; void pull(int i) { tree[i] = tree[2 * i] + tree[2 * i + 1]; } void push(int i) { if (!lazy[i]) return; tree[i].swap(); if (i < treeN) { lazy[2 * i].flip(); lazy[2 * i + 1].flip(); } lazy[i] = 0; } val operation(int i, int l, int r, int ql, int qr, int op) { push(i); if (r < ql || qr < l) return {}; if (ql <= l && r <= qr) { if (op == 1) { lazy[i] = 1; push(i); } return tree[i]; } int mid = (l + r) / 2; val res = operation(2 * i, l, mid, ql, qr, op) + operation(2 * i + 1, mid + 1, r, ql, qr, op); pull(i); return res; }; int calc01s(int i) { if (i >= n) { return term01[i] = 1; } int all = sz(children[i]); for (int j : children[i]) { int v = calc01s(j); all *= v; all %= MOD; } return term01[i] = all; } vi calc(int i) { if (i >= n) { vs[i - n] = 1; return {i - n}; } int c = sz(children[i]); vi prod, prefProd(c + 1, 1), sufProd(c + 1, 1); vvi leafs; for (int j : children[i]) { leafs.pb(move(calc(j))); prod.pb(term01[j]); } loop(c, j) { prefProd[j + 1] = prefProd[j] * prod[j]; prefProd[j + 1] %= MOD; } rev(c, j) { sufProd[j] = sufProd[j + 1] * prod[j]; sufProd[j] %= MOD; } vi res; loop(c, j) { int mult = (prefProd[j] * sufProd[j + 1]) % MOD; for (int ix : leafs[j]) { vs[ix] = (vs[ix] * mult) % MOD; res.pb(ix); } } // return res; return move(res); } void init(i32 N, i32 M, vi32 P, vi32 A) { n = N; m = M; while (treeN < m) treeN *= 2; tree.resize(2 * treeN); lazy.resize(2 * treeN); children = vvi(N); term01 = vi(N + M); vs = vi(M); loop(sz(P), i) { if (i == 0) continue; children[P[i]].pb(i); } calc01s(0); calc(0); loop(m, i) { tree[treeN + i].totalV = vs[i]; if (A[i]) tree[treeN + i].v = vs[i]; } rev(treeN, i) pull(i); } i32 count_ways(i32 L, i32 R) { operation(1, 0, treeN - 1, L - n, R - n, 1); return (i32)operation(1, 0, treeN - 1, 0, m - 1, 0).v; }

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

circuit.cpp: In function 'vi calc(long long int)':
circuit.cpp:145:14: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
  145 |   return move(res);
      |          ~~~~^~~~~
circuit.cpp:145:14: note: remove 'std::move' call
#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...