Submission #1078705

#TimeUsernameProblemLanguageResultExecution timeMemory
1078705Gromp15Digital Circuit (IOI22_circuit)C++17
18 / 100
3076 ms3928 KiB
#include <bits/stdc++.h> #define ll long long #define sz(x) (int)x.size() #define ar array #include "circuit.h" using namespace std; const int mod = int(1e9) + 2022; void fadd(int &a, int b) { a += b; if (a >= mod) a -= mod; } void fsub(int &a, int b) { a -= b; if (a < 0) a += mod; } vector<int> p, a, sub, sub2; vector<vector<int>> adj; int n, m; void init(int N, int M, std::vector<int> P, std::vector<int> A) { n = N, m = M; p = P, a = A; adj.resize(N), sub.resize(N+M, 1), sub2.resize(N+M, 1); for (int i = 1; i < N + M; i++) adj[P[i]].emplace_back(i); for (int i = N-1; i >= 0; i--) { sub[i] = sz(adj[i]); int cur = sz(adj[i]); vector<int> pref(cur), suff(cur); for (int j = 0; j < cur; j++) { pref[j] = suff[j] = sub[adj[i][j]]; } for (int j = 1; j < cur; j++) pref[j] = (ll)pref[j-1] * pref[j] % mod; for (int j = cur-2; j >= 0; j--) suff[j] = (ll)suff[j+1] * suff[j] % mod; for (int j = 0; j < cur; j++) { int u = adj[i][j]; sub[i] = (ll)sub[i] * sub[u] % mod; sub2[u] = (ll)(j ? pref[j-1] : 1) * (j+1 < cur ? suff[j+1] : 1) % mod; } } } int count_ways(int L, int R) { for (int i = L; i <= R; i++) a[i - n] ^= 1; vector<int> dp(n+m); for (int i = n+m-1; i >= 0; i--) { if (i >= n) dp[i] = a[i-n]; else { int N = sz(adj[i]); for (int u : adj[i]) { fadd(dp[i], (ll)dp[u] * sub2[u] % mod); } } } return dp[0]; }

Compilation message (stderr)

circuit.cpp: In function 'int count_ways(int, int)':
circuit.cpp:49:8: warning: unused variable 'N' [-Wunused-variable]
   49 |    int N = sz(adj[i]);
      |        ^
#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...