Submission #1223003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223003		abdelhakim	Digital Circuit (IOI22_circuit)	C++20	100 / 100	690 ms	87508 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>
#define ll long long
#define mod 1000002022
#define dbg(x) cerr<<#x << ' ' << x << endl;
using namespace std;
#include <vector>
vector<vector<ll>> adj;
ll n,m;
vector<ll> a;
vector<ll> c;
map<pair<ll,ll>, ll> w;
ll maxn=3e5;
vector<pair<ll,ll>> tree(4*maxn+3);
vector<bool> lazy(4*maxn+3);

void intachir(ll node,ll l, ll r)
{
  if(lazy[node])
  {
    swap(tree[node].first,tree[node].second);
    lazy[node]=false;
    if(l!=r) 
    {
      lazy[node*2+1]=lazy[node*2+1]^1;
      lazy[node*2+2]=lazy[node*2+2]^1;
    }
  }
}
void build(ll node, ll l, ll r)
{
  if(l==r)
  {
    if(a[l]==1) tree[node].first=c[l]%mod;
    else tree[node].second=c[l]%mod;
    return;
  }
  ll mid=(l+r)/2;
  build(node*2+1,l,mid);
  build(node*2+2,mid+1,r);
  tree[node].first=(tree[node*2+1].first+tree[node*2+2].first)%mod;
  tree[node].second=(tree[node*2+1].second+tree[node*2+2].second)%mod;
}
void update(ll node, ll l, ll r, ll x, ll y)
{
  intachir(node,l,r);
  if(max(x,l) > min(r,y))return;
  if(x<=l && r<=y)
  {
    lazy[node]=1;
    intachir(node,l,r);
    return;
  }
  ll mid=(l+r)>>1;
  update(node*2+1,l,mid,x,y);
  update(node*2+2,mid+1,r,x,y);
  tree[node].first=(tree[node*2+1].first+tree[node*2+2].first)%mod;
  tree[node].second=(tree[node*2+1].second+tree[node*2+2].second)%mod;
}
ll dfs(ll node, ll par)
{
  if(adj[node].size()==1 && node!=par) return 1;
  vector<ll> v(adj[node].size());
  vector<ll> p(adj[node].size());
  vector<ll> s(adj[node].size());
  ll d=adj[node].size()-1;
  if(node==par)d++;
  for (int i=0;i<adj[node].size();i++)
  {
    if(adj[node][i]==par)
    {
      v[i]=1;
      p[i]=v[i];
      if(i>0)p[i]*=p[i-1];
      continue;
    }
    v[i]=dfs(adj[node][i],node);
    p[i]=v[i];
    if(i>0)
    {
      p[i]*=p[i-1];
      p[i]%=mod;
    }
  }
  for (int i=adj[node].size()-1;i>=0;i--)
    {
      s[i]=v[i];
      if(i!=adj[node].size()-1)
      {
        s[i]*=s[i+1];
        s[i]%=mod;
      }
    }
    
    for (int i=0;i<adj[node].size();i++)
    {
      if(adj[node][i]==par)continue;
      ll lft=1;
      ll r=1;
      if(i>0)lft=p[i-1];
      if(i<adj[node].size()-1)r=s[i+1];
      ll val=lft*r%mod;
      w[{node,adj[node][i]}]=val;
      w[{adj[node][i],node}]=val;
    }
  ll pr=p.back()*d%mod;
  return pr;
}
void calculate(ll node, ll par, ll pr)
{
  if(adj[node].size()==1 && node!=par)
  {
    c[node-n]=pr;
    return;
  }
  for (auto &&e : adj[node])
  {
    if(e==par)continue;
   calculate(e,node,pr*w[{node,e}]%mod); 
  }
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
  n=N;
  m=M;
  c.assign(m,1);
  adj.resize(n+m);
  for (int i=0;i<m;i++)a.push_back(A[i]);
  for (int i=1;i<n+m;i++)
  {
    adj[i].push_back(P[i]);
    adj[P[i]].push_back(i);
  }
  dfs(0,0);
  calculate(0,0,1);
  build(0,0,m-1);
}

int count_ways(int L, int R) {
  update(0,0,m-1,L-n,R-n);
  intachir(0,0,m-1);
  return tree[0].first;
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11