Submission #988456

#TimeUsernameProblemLanguageResultExecution timeMemory
988456siewjh디지털 회로 (IOI22_circuit)C++17
100 / 100
894 ms40876 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 200005; const ll mod = 1'000'002'022; vector<int> adj[MAXN]; ll sbt[MAXN], lv[MAXN]; bool st[MAXN]; struct node{ int s, e, m; ll v0, v1; bool lazy; node *l, *r; node (int _s, int _e){ s = _s, e = _e, m = (s + e) >> 1, v0 = 0, v1 = 0, lazy = 0; if (s == e) (st[s] ? v1 : v0) = lv[s]; else{ l = new node(s, m); r = new node(m + 1, e); v0 = l->v0 + r->v0; v1 = l->v1 + r->v1; } } void push(){ swap(v0, v1); lazy = !lazy; } void propo(){ if (s == e) return; if (lazy){ l->push(); r->push(); lazy = 0; } } void update(int x, int y){ if (x == s && y == e){ push(); return; } propo(); if (y <= m) l->update(x, y); else if (x > m) r->update(x, y); else{ l->update(x, m); r->update(m + 1, y); } propo(); v0 = l->v0 + r->v0; v1 = l->v1 + r->v1; } } *root; void dfs(int x){ sbt[x] = max(1, (int)(adj[x].size())); for (auto nn : adj[x]){ dfs(nn); sbt[x] = sbt[x] * sbt[nn] % mod; } } void dfs2(int x, ll uv){ int asz = adj[x].size(); vector<ll> lp(asz + 2), rp(asz + 2); lp[0] = 1; rp[asz + 1] = 1; for (int i = 1; i <= asz; i++) lp[i] = lp[i - 1] * sbt[adj[x][i - 1]] % mod; for (int i = asz; i >= 1; i--) rp[i] = rp[i + 1] * sbt[adj[x][i - 1]] % mod; for (int i = 1; i <= asz; i++){ int nn = adj[x][i - 1]; dfs2(nn, uv * lp[i - 1] % mod * rp[i + 1] % mod); } lv[x] = uv; } void init(int N, int M, vector<int> P, vector<int> A) { int tot = N + M; for (int i = 1; i < tot; i++) adj[P[i]].push_back(i); for (int i = N; i < tot; i++) st[i] = A[i - N]; dfs(0); dfs2(0, 1); root = new node(N, tot - 1); } int count_ways(int L, int R) { root->update(L, R); return root->v1 % mod; }
#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...