Submission #838342

#TimeUsernameProblemLanguageResultExecution timeMemory
838342fatemetmhrDigital Circuit (IOI22_circuit)C++17
2 / 100
460 ms8332 KiB
// Be name khoda // #include "circuit.h" #include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define debug(x) cerr << "(" << (#x) << "): " << (x) << endl; #define all(x) x.begin(), x.end() #define pb push_back #define mp make_pair #define fi first #define se second typedef long long ll; const int mod = 1000002022; const int maxn5 = 2e5 + 10; const int maxnt = 1e6 + 10; vector <int> adj[maxn5]; int n, m; ll val[maxn5], all[maxn5]; void fix(int &a){ if(a >= mod) a -= mod; } namespace seg{ int sum[maxnt][2]; bool lazy[maxnt]; void toggle(int l, int r, int lq, int rq, int v){ if(rq <= l || r <= lq) return; if(lq <= l && r <= rq){ lazy[v] ^= 1; swap(sum[v][0], sum[v][1]); return; } int mid = (l + r) >> 1; toggle(l, mid, lq, rq, v * 2); toggle(mid, r, lq, rq, v * 2 + 1); fix(sum[v][0] = sum[v * 2][0] + sum[v * 2 + 1][0]); fix(sum[v][1] = sum[v * 2][1] + sum[v * 2 + 1][1]); if(lazy[v]) swap(sum[v][0], sum[v][1]); return; debug(l); debug(r); debug(lq); debug(rq); debug(sum[v][0]); debug(sum[v][1]); debug(lazy[v]); debug(sum[v * 2 + 1][0]); } void build(int l, int r, int v){ if(r - l == 1){ sum[v][0] = 0; sum[v][1] = val[l + n]; return; } int mid = (l + r) >> 1; build(l, mid, v * 2); build(mid, r, v * 2 + 1); fix(sum[v][0] = sum[v * 2][0] + sum[v * 2 + 1][0]); fix(sum[v][1] = sum[v * 2][1] + sum[v * 2 + 1][1]); } } void dfs2(int v){ ll x = val[v]; for(auto u : adj[v]){ val[u] = x; x = x * all[u] % mod; } x = val[v]; reverse(all(adj[v])); for(auto u : adj[v]){ val[u] = val[u] * x % mod; dfs2(u); x = x * all[u] % mod; } return; debug(v); debug(all[v]); debug(val[v]); debug(val[6]); } void dfs1(int v){ all[v] = max(1, int(adj[v].size())); for(auto u : adj[v]){ dfs1(u); all[v] = all[v] * all[u] % mod; } } void init(int N, int M, std::vector<int> p, std::vector<int> a) { n = N; m = M; for(int i = 1; i < n + m; i++) adj[p[i]].pb(i); val[0] = 1; dfs1(0); dfs2(0); seg::build(0, m, 1); for(int i = 0; i < m; i++){ //debug(i); //debug(val[i + n]); if(a[i]) seg::toggle(0, m, i, i + 1, 1); } } int count_ways(int l, int r) { l -= n; r -= n; seg::toggle(0, m, l, r + 1, 1); return seg::sum[1][0]; }
#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...