Submission #1239520

#TimeUsernameProblemLanguageResultExecution timeMemory
1239520AlperenT_Digital Circuit (IOI22_circuit)C++20
46 / 100
3017 ms26584 KiB
#include "circuit.h" #include <vector> #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #define pb push_back #define F first #define pii pair<int,int> #define all(a) a.begin(),a.end() #define S second #define sz(a) (int)a.size() #define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++) #define per(i , a , b) for(int i = (a) ; i >= (b) ; i--) #define ld double #define int long long using namespace std ; const int maxn = 1e6 + 10 , inf = 1e9+ 10 , mod = 1000002022 ; int a[maxn] , n ,m , ans[maxn]; vector <int >G[maxn] ; int sb[maxn] ; void dfs2(int v){ sb[v] =1 ; if(v < n)sb[v] = sz(G[v]) ; for(int u : G[v]){ dfs2(u) ; sb[v] = sb[v] * sb[u] % mod ; } } void dfs(int v , int z =1 ){ vector <int> pr , sf; pr.pb(1); for(int u : G[v]){ pr.pb(sb[u]) ; sf.pb(sb[u]) ; }; sf.pb(1); rep(i , 1 ,sz(pr)-1){ pr[i] = pr[i-1] * pr[i] % mod ; } per(i , sz(sf)-2 , 0){ sf[i] = sf[i+1] * sf[i] % mod ; } if(v >= n)ans[v-n] = z ; int c =0 ; for(int u : G[v]){ dfs(u , z * pr[c] % mod * sf[c+1] % mod) ; c++ ; } } void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) { n = N ; m = M ; rep(i ,1, n+m-1){ G[P[i]].pb(i) ; } dfs2(0); dfs(0) ; rep(i , 0 ,m-1)a[i] = A[i] ; } int32_t count_ways(int32_t L, int32_t R) { int sm =0 ; rep(i , L-n , R-n){ a[i] ^= 1; } rep(i , 0 ,m-1){ if(a[i] == 1)sm= (sm + ans[i]) % mod ; } return sm; }
#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...