Submission #1222873

#TimeUsernameProblemLanguageResultExecution timeMemory
1222873cpdreamerDigital Circuit (IOI22_circuit)C++20
46 / 100
3074 ms6912 KiB
#include "circuit.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; const long long INF = 1e17; typedef long long ll; const ll MOD = 1000002022; #define S second #define F first #define pb push_back #define V vector #define all(v) v.begin(), v.end() V<int>adj[(int)1e5+1]; ll dp[(int)2e5+1]; ll dp1[(int)2e5+1]; int a[(int)2e5+1]; ll b[(int)2e5+1]; int na,ma; ll add(ll a,ll b) { return ((a%MOD)+(b%MOD))%MOD; } ll mul(ll a,ll b) { return ((a%MOD*(b%MOD)))%MOD; } void dfs(int n,int p) { ll ch=(ll)adj[n].size()-1+(n==0); if (ch==0) { dp[n]=1; return; } dp[n]=ch; for (auto u:adj[n]) { if (u==p)continue; dfs(u,n); dp[n]=mul(dp[n],dp[u]); } } void dfs1(int n,int p) { ll ch=(ll)adj[n].size()-1+(n==0); if (ch==0) { return; } V<ll>pref(ch); V<ll>suff(ch); int c=0; for (auto u:adj[n]) { if (u==p)continue; pref[c]=dp[u]; suff[c]=dp[u]; c++; } for (int i=1;i<c;i++) { pref[i]=mul(pref[i-1],pref[i]); } for (int i=c-2;i>=0;i--) { suff[i]=mul(suff[i+1],suff[i]); } c=0; for (auto u:adj[n]) { if (u==p)continue; ll x=1; if (c>0) { x=mul(x,pref[c-1]); } if (c<ch-1) { x=mul(x,suff[c+1]); } dp1[u]=mul(x,dp1[n]); c++; } for (auto u:adj[n]) { if (u==p)continue; dfs1(u,n); } } void init(int N, int M, std::vector<int> P, std::vector<int> A) { na=N; ma=M; for (int i =1;i<N+M;i++) { adj[i].pb(P[i]); adj[P[i]].pb(i); } dp1[0]=1; dfs(0,-1); dfs1(0,-1); for (int i=0;i<M;i++) { a[i+N]=A[i]; b[i+N]=dp1[i+N]; } } int count_ways(int L, int R) { for (int i=L;i<=R;i++) { a[i]^=1; } ll x=0; for (int i=0;i<ma;i++) { if (a[i+na]==1) { x=add(x,b[i+na]); } } x%=MOD; return (int)x; }
#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...