Submission #836313

#TimeUsernameProblemLanguageResultExecution timeMemory
836313ma_moutahid디지털 회로 (IOI22_circuit)C++17
2 / 100
3031 ms4560 KiB
#include "circuit.h" #include<bits/stdc++.h> #include "circuit.h" using namespace std; #define vi vector<int> #define vii vector<vi> #define ll long long #define vl vector<ll> #include <cassert> #include <cstdio> int n,m; vii g; vl ways; vl wb; int mod=1000002022; ll sum(ll a, ll b){ return (a+b)%mod; } ll diff(ll a, ll b){ return(a-b+mod)%mod; } void init(int N, int M, std::vector<int> P, std::vector<int> A) { n=N; m=M; g.resize(N+M); ways.resize(M+N); wb.resize(M+N); for(int i=1 ;i<N+M;i++){ g[P[i]].push_back(i); } for(int i=N;i<N+M;i++){ ways[i]=A[i-N]; wb[i]=!ways[i]; } } void dfs(int node){ for(int child:g[node]){ if(child>=n)continue; dfs(child); } int p=g[node].size(); vl v(p+1); v[0]=1; for(int child:g[node]){ vl copy(p+1); for(int i=0;i<=p;i++){ if(i<p){ copy[i+1]+=v[i+1]*wb[child]+v[i]*ways[child]; copy[i+1]%=mod; } } copy[0]=v[0]*wb[child]; v=copy; } vl cum(p+1); cum[0]=v[0]; for(int i=1;i<=p;i++){ cum[i]=sum(cum[i-1],v[i]); } wb[node]=0; ways[node]=0; for(int i=1;i<=p;i++){ wb[node]+=cum[i-1]; wb[node]%=mod; ways[node]+=diff(cum[p],cum[i-1]); ways[node]%=mod; } } int count_ways(int L, int R) { for(int i=L;i<=R;i++){ ways[i]=!ways[i]; wb[i]=!wb[i]; } dfs(0); return ways[0]; }
#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...