Submission #1074655

#TimeUsernameProblemLanguageResultExecution timeMemory
1074655fv3Digital Circuit (IOI22_circuit)C++17
0 / 100
435 ms3928 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; int cnt = 0; ll a1, a2; 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); a1 = a2 = -1; } int count_ways(int L, int R) { cnt++; if (cnt%2 == 1 && a1 != -1) { return a1; } else if (cnt%2 == 0 && a2 != -1) { return a2; } L -= N; R -= N; for (int i = L; i <= R; i++) A[i] ^= 1; DFS(0); if (cnt%2) a1 = nodes[0].first; else a2 = nodes[0].first; 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...