Submission #1074667

#TimeUsernameProblemLanguageResultExecution timeMemory
1074667fv3Digital Circuit (IOI22_circuit)C++17
4 / 100
722 ms7768 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1000002022ll; int N, M; vector<int> A; vector<vector<int>> adj; vector<pair<ll, ll>> nodes; void DFS(int index) { if (index >= N) { if (A[index - N]) nodes[index] = {1, 0}; else nodes[index] = {0, 1}; return; } for (auto node : adj[index]) { DFS(node); } const auto l = nodes[adj[index][0]]; const auto r = nodes[adj[index][1]]; nodes[index] = { (2 * l.first * r.first + l.first * r.second + l.second * r.first ) % MOD, (2 * l.second * r.second + l.first * r.second + l.second * r.first ) % MOD }; } void init(int N_, int M_, vector<int> P, vector<int> A_) { N = N_; M = M_; A = A_; adj = vector<vector<int>>(N); for (int i = 1; i < N + M; i++) adj[P[i]].push_back(i); nodes = vector<pair<ll, ll>>(N+M); DFS(0); } int count_ways(int L, int R) { A[L - N] ^= 1; while (1) { if (L >= N) { if (A[L - N]) nodes[L] = {1, 0}; else nodes[L] = {0, 1}; L = (L - 1) / 2; continue; } const auto l = nodes[adj[L][0]]; const auto r = nodes[adj[L][1]]; nodes[L] = { (2 * l.first * r.first + l.first * r.second + l.second * r.first ) % MOD, (2 * l.second * r.second + l.first * r.second + l.second * r.first ) % MOD }; if (L == 0) break; L = (L - 1) / 2; } return nodes[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...