Submission #1222887

#TimeUsernameProblemLanguageResultExecution timeMemory
1222887cpdreamerDigital Circuit (IOI22_circuit)C++20
100 / 100
453 ms41380 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)2e5+1]; ll dp[(int)2e5+1]; ll dp1[(int)2e5+1]; int na,ma; ll md(ll a) { return ((a%MOD)+MOD)%MOD; } ll dif(ll a,ll b) { return md(md(a)-md(b)); } ll add(ll a,ll b) { return ((a%MOD)+(b%MOD))%MOD; } ll mul(ll a,ll b) { return ((a%MOD*(b%MOD)))%MOD; } struct segtree { private: struct node { ll sum; ll ans; }; node merge(node a,node b) { return {add(a.sum,b.sum),add(a.ans,b.ans)}; } node single(pair<ll,ll>v) { return {v.F,mul(v.F,v.S)}; } node neutral={0,0}; node modification( node a,int v) { if (v==0) { return a; } return {a.sum,dif(a.sum,a.ans)}; } int operation_modifer(int a,int b) { return a^b; } public: int size; V<node>query; V<int>operation; void init(int n) { size=1; while (size<n)size*=2; query.assign(2*size,neutral); operation.assign(2*size,0); } void build(V<ll>&a,V<ll>&b,int x,int lx,int rx) { if (rx-lx==1) { if (lx<a.size()) { query[x]=single({a[lx],b[lx]}); } return; } int m=(lx+rx)/2; build(a,b,2*x+1,lx,m); build(a,b,2*x+2,m,rx); query[x]=merge(query[2*x+1],query[2*x+2]); } void build(V<ll>&a,V<ll>&b) { build(a,b,0,0,size); } void toggle(int l,int r,int v,int x,int lx,int rx) { if (lx>=r || rx<=l) { return; } if (l<=lx && rx<=r) { query[x]=modification(query[x],v); operation[x]=operation_modifer ( operation[x],v ); return; } int m=(lx+rx)/2; toggle(l,r,v,2*x+1,lx,m); toggle(l,r,v,2*x+2,m,rx); query[x]=modification(merge(query[2*x+1],query[2*x+2]),operation[x]); } void toggle(int l,int r) { toggle(l,r,1,0,0,size); } }; 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); } } segtree tree1; 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); } V<ll>a(M); for (int i=0;i<M;i++) { a[i]=A[i]; } dp1[0]=1; dfs(0,-1); dfs1(0,-1); tree1.init(M); V<ll>B(M); for (int i=0;i<M;i++) { B[i]=dp1[i+N]; } tree1.build(B,a); } int count_ways(int L, int R) { tree1.toggle(L-na,R-na+1); return (int)tree1.query[0].ans; }
#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...