Submission #1238558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238558		Muhammad_Aneeq	Digital Circuit (IOI22_circuit)	C++17	6 / 100	314 ms	32756 KiB

circuit

#include "circuit.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

#define ll long long

struct node
{
    ll on=0,of=0,swp=0;
};
int const NPM=2e5+10,mod=1000002022;
vector<int>nei[NPM]={};
long long dp[NPM]={};
vector<long long>pre[NPM]={};
vector<long long>suf[NPM]={};
int ans[NPM]={};
bool op[NPM]={};
node seg[4*NPM]={};
int n,m;

long long mul(ll a,ll b)
{
    return (a*b)%mod;
}
long long add(ll a,ll b)
{
    return (a+b)%mod;
}
void build(int i,int st,int en)
{
    if (st==en)
    {
        if (op[st])
            seg[i].on=ans[st];
        else
            seg[i].of=ans[st];
        return;
    }
    int mid=(st+en)/2;
    build(i*2,st,mid);
    build(i*2+1,mid+1,en);
    seg[i].on=add(seg[i*2].on,seg[i*2+1].on);
    seg[i].of=add(seg[i*2].of,seg[i*2+1].of);
}
void push(int i)
{
    for (int j=2*i;j<=2*i+1;j++)
    {
        seg[j].swp^=1;
        swap(seg[j].on,seg[j].of);
    }
    seg[i].swp=0;
}
void update(int i,int st,int en,int l,int r)
{
    if (st>=l&&en<=r)
    {
        swap(seg[i].on,seg[i].of);
        seg[i].swp=1;
        return;
    }
    if (st>r||en<l)
        return;
    if (seg[i].swp)
        push(i);
    int mid=(st+en)/2;
    update(i*2,st,mid,l,r);update(i*2+1,mid+1,en,l,r);
    seg[i].on=add(seg[i*2].on,seg[i*2+1].on);
    seg[i].of=add(seg[i*2].of,seg[i*2+1].of);
}
void comp(int u,ll val=1)
{
    if (u>=n)
        ans[u-n]=val;
    int sz=nei[u].size();
    for (int i=0;i<sz;i++)
        comp(nei[u][i],mul(mul(val,pre[u][i]),suf[u][i+1]));
}
void dfs(int u)
{
    dp[u]=1;
    pre[u]={1};
    suf[u]={1};
    if (nei[u].size()==0)
        return;
    for (auto i:nei[u])
    {
        dfs(i);
        dp[u]=mul(dp[i],dp[u]);
        pre[u].push_back(mul(pre[u].back(),dp[i]));
    }
    dp[u]=mul(dp[u],nei[u].size());
    int sz=nei[u].size();
    for (int i=sz-1;i>=0;i--)
        suf[u].push_back(mul(suf[u].back(),dp[nei[u][i]]));
    reverse(begin(suf[u]),end(suf[u]));
}
void init(int N, int M, vector<int> P, vector<int> A) 
{
    n=N;
    m=M;
    for (int i=1;i<n+m;i++)
        nei[P[i]].push_back(i);
    dfs(0);
    comp(0);
    for (int i=0;i<m;i++)
        op[i]=A[i];
    build(1,0,m-1);
}
int count_ways(int L, int R) 
{
    update(1,0,m-1,L-n,R-n);
    return seg[1].on;
}

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