Submission #1057282

#TimeUsernameProblemLanguageResultExecution timeMemory
1057282esomerDigital Circuit (IOI22_circuit)C++17
0 / 100
404 ms7356 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1000002022; struct segTree{ vector<pair<ll, ll>> v; vector<int> upd; int sz; void init(int n){ sz = 1; while(sz < n) sz *= 2; v.assign(2 * sz, {0, 0}); upd.assign(2 * sz, 0); } void set(int i, pair<ll, ll> p, int x, int lx, int rx){ if(rx - lx == 1){ v[x] = p; return; } int m = (lx + rx) / 2; if(i < m) set(i, p, 2 * x + 1, lx, m); else set(i, p, 2 * x + 2, m, rx); v[x].first = v[2 * x + 1].first + v[2 * x + 2].first; v[x].second = v[2 * x + 1].second + v[2 * x + 2].second; } void set(int i, pair<ll, ll> p){ set(i, p, 0, 0, sz); } void push(int x){ if(upd[x]){ upd[2 * x + 1] ^= 1; swap(v[2 * x + 1].first, v[2 * x + 1].second); upd[2 * x + 2] ^= 1; swap(v[2 * x + 2].first, v[2 * x + 2].second); } } void change(int l, int r, int x, int lx, int rx){ if(lx >= l && rx <= r){ swap(v[x].first, v[x].second); upd[x] ^= 1; return; }else if(lx >= r || rx <= l) return; int m = (lx + rx) / 2; push(x); change(l, r, 2 * x + 1, lx, m); change(l, r, 2 * x + 2, m, rx); v[x].first = v[2 * x + 1].first + v[2 * x + 2].first; v[x].second = v[2 * x + 1].second + v[2 * x + 2].second; } void change(int l, int r){ change(l, r, 0, 0, sz); } }; void getSub(int x, vector<vector<int>>& adj, vector<ll>& subtree){ ll opt = (int)adj[x].size(); subtree[x] = opt; for(int node : adj[x]){ getSub(node, adj, subtree); if(!adj[node].empty()){ subtree[x] *= subtree[node]; subtree[x] %= MOD; } } // cout << "x " << x << " subtree " << subtree[x] << endl; } void DFS(int x, vector<vector<int>>& adj, vector<ll>& subtree, vector<ll>& dp, ll curr = 1){ int sz = (int)adj[x].size(); dp[x] = curr; if(!sz) return; vector<ll> suf(sz+1, 1); for(int i = sz - 1; i >= 0; i--){ suf[i] = suf[i+1] * max(subtree[adj[x][i]], 1ll); suf[i] %= MOD; } ll nw = 1; for(int i = 0; i < sz; i++){ ll all = nw * suf[i+1]; DFS(adj[x][i], adj, subtree, dp, (curr * all) % MOD); nw *= max(subtree[adj[x][i]], 1ll); nw %= MOD; } } segTree st; void init(int N, int M, vector<int> P, vector<int> A) { vector<vector<int>> adj(N+M); for(int i = 1; i < N + M; i++){ adj[P[i]].push_back(i); } vector<ll> subtree(N+M); getSub(0, adj, subtree); vector<ll> dp(N+M, 0); DFS(0, adj, subtree, dp); st.init(N+M); for(int i = N; i < N+M; i++){ // cout << "i " << i << " dp " << dp[i] << "\n"; pair<ll, ll> p = {dp[i], 0}; if(!A[i-N]) swap(p.first, p.second); st.set(i, p); } } int count_ways(int L, int R) { st.change(L, R + 1); return st.v[0].first; }
#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...