| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 945041 | abczz | 디지털 회로 (IOI22_circuit) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "circuit.h"
#include <iostream>
#include <vector>
#include <array>
#define ll long long
using namespace std;
vector <ll> adj[200000];
bool B[200000];
array<ll, 2> st[400000];
bool lazy[400000];
ll n, m, sz[200000], X[200000], M = 1e9 + 2022;
void dfs(ll u) {
sz[u] = adj[u].size();
for (auto v : adj[u]) {
dfs(v);
sz[u] *= sz[v];
sz[u] %= M;
}
if (!sz[u]) sz[u] = 1;
}
void solve(ll u, ll w) {
X[u] = w;
vector <ll> pref, suf;
pref.resize(adj[u].size());
suf.resize(adj[u].size());
for (int i=0; i<adj[u].size(); ++i) {
pref[i] = sz[adj[u][i]];
if (i) {
pref[i] *= pref[i-1];
pref[i] %= M;
}
}
for (int i=adj[u].size()-1; i>=0; --i) {
suf[i] = sz[adj[u][i]];
if (i != adj[u].size()-1) {
suf[i] *= suf[i+1];
suf[i] %= M;
}
}
for (int i=0; i<adj[u].size(); ++i) {
solve(adj[u][i], (w * (((i ? pref[i-1] : 1) * (i != adj[u].size()-1 ? suf[i+1] : 1)) % M))%M);
}
}
void build(ll id, ll l, ll r) {
if (l == r) {
st[id] = {X[l], 0};
if (B[l]) swap(st[id][0], st[id][1]);
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id][0] = st[id*2][0] + st[id*2+1][0];
st[id][1] = st[id*2][1] + st[id*2+1][1];
}
void push(ll id) {
if (lazy[id]) {
lazy[id*2] ^= 1;
lazy[id*2+1] ^= 1;
swap(st[id*2][0], st[id*2][1]);
swap(st[id*2+1][0], st[id*2+1][1]);
lazy[id] = 0;
}
}
void update(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql) return;
else if (ql <= l && r <= qr) {
lazy[id] ^= 1;
swap(st[id][0], st[id][1]);
return;
}
ll mid = (l+r)/2;
push(id);
update(id*2, l, mid, ql, qr);
update(id*2+1, mid+1, r, ql, qr);
st[id][0] = st[id*2][0] + st[id*2+1][0];
st[id][1] = st[id*2][1] + st[id*2+1][1];
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N, m = M;
for (int i=N; i<N+M; ++i) {
B[i] = A[i-N];
}
for (int i=1; i<P.size(); ++i) {
adj[P[i]].push_back(i);
}
dfs(0);
solve(0, 1);
build(1, n, n+m-1);
}
int count_ways(int L, int R) {
update(1, n, n+m-1, L, R);
return st[1][1];
}
int main() {
init(3, 4, {-1, 0, 1, 2, 1, 1, 0}, {1, 0, 1, 0});
cout << count_ways(3, 4) << '\n';
cout << count_ways(4, 5) << '\n';
cout << count_ways(3, 6) << '\n';
}