Submission #1222861

#TimeUsernameProblemLanguageResultExecution timeMemory
1222861cpdreamerDigital Circuit (IOI22_circuit)C++20
46 / 100
3050 ms6368 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]; bool f[(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; if (a[n]) { f[n]=true; } return; } for (auto u:adj[n]) { if (u==p)continue; dfs(u,n); } ll x=1; for (auto u:adj[n]) { if (u==p)continue; x=mul(x,dp[u]); f[n]|=f[u]; } if (!f[n]) { x=mul(x,ch); } dp[n]=x; } 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); } for (int i=0;i<M;i++) { a[i+N]=0; } for (int i=0;i<M;i++) { a[i+N]=1; for (int j=0;j<N+M;j++) { f[j]=false; } dfs(0,-1); b[i+N]=dp[0]; a[i+N]=0; } for (int i=0;i<M;i++){ a[i+N]=A[i]; } } 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...