| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 790524 | borisAngelov | 디지털 회로 (IOI22_circuit) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "circuit.h"
#include "stub.cpp"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
const long long mod = 1e9 + 2022;
int n, m;
vector<int> g[maxn];
long long contribution[maxn];
long long subtree[maxn];
void dfs(int node, int dep)
{
if (g[node].empty())
{
subtree[node] = 1;
return;
}
subtree[node] = 1LL * (g[node].size());
for (int i = 0; i < g[node].size(); ++i)
{
dfs(g[node][i], dep + 1);
subtree[node] *= subtree[g[node][i]];
subtree[node] %= mod;
}
}
void dfs2(int node, long long from_parent)
{
if (g[node].empty())
{
contribution[node] = from_parent;
return;;
}
vector<long long> preffix(g[node].size() + 5, 1);
vector<long long> suffix(g[node].size() + 5, 1);
for (int i = 0; i < g[node].size(); ++i)
{
if (i == 0)
{
preffix[i] = 1;
}
else
{
preffix[i] = preffix[i - 1] * subtree[g[node][i - 1]];
preffix[i] %= mod;
}
}
suffix[g[node].size()] = 1LL;
for (int i = g[node].size() - 1; i >= 0; --i)
{
suffix[i] = (suffix[i + 1] * subtree[g[node][i]]) % mod;
}
for (int i = 0; i < g[node].size(); ++i)
{
long long product = (preffix[i] * suffix[i + 1]) % mod;
dfs2(g[node][i], (from_parent * product) % mod);
}
}
long long preffix[maxn];
long long get_sum(int l, int r)
{
if (l == 0)
{
return preffix[r];
}
return (preffix[r] - preffix[l - 1] + mod) % mod;
}
struct segment_tree
{
struct vertex
{
long long sum;
bool lazy;
vertex()
{
sum = 0;
lazy = false;
}
vertex(long long _sum, bool _lazy)
{
sum = _sum;
lazy = _lazy;
}
};
vertex tree[4 * maxn];
void push_lazy(int node, int l, int r)
{
if (tree[node].lazy == true)
{
tree[node].sum = (get_sum(l, r) - tree[node].sum + mod) % mod;
if (l != r)
{
tree[2 * node].lazy = 1 - tree[2 * node].lazy;
tree[2 * node + 1].lazy = 1 - tree[2 * node + 1].lazy;
}
tree[node].lazy = false;
}
}
void update(int node, int l, int r, int ql, int qr)
{
push_lazy(node, l, r);
if (l > qr || r < ql)
{
return;
}
if (ql <= l && r <= qr)
{
tree[node].lazy = true;
push_lazy(node, l, r);
return;
}
int mid = (l + r) / 2;
update(2 * node, l, mid, ql, qr);
update(2 * node + 1, mid + 1, r, ql, qr);
tree[node].sum = (tree[2 * node].sum + tree[2 * node + 1].sum) % mod;
}
void update(int l, int r)
{
update(1, 0, m - 1, l, r);
}
};
segment_tree tree;
void init(int N, int M, vector<int> P, vector<int> A)
{
n = N;
m = M;
for (int i = 1; i < P.size(); ++i)
{
g[P[i]].push_back(i);
}
dfs(0, 0);
dfs2(0, 1);
for (int i = 0; i < m; ++i)
{
preffix[i] = contribution[i + n];
if (i > 0)
{
preffix[i] += preffix[i - 1];
}
preffix[i] %= mod;
}
for (int i = 0; i < m; ++i)
{
if (A[i] == 1)
{
tree.update(i, i);
}
}
}
int count_ways(int L, int R)
{
int l = L - n;
int r = R - n;
tree.update(l, r);
return tree.tree[1].sum;
}