Submission #627460

#	Time	Username	Problem	Language	Result	Execution time	Memory
627460		Kaitokid	Digital Circuit (IOI22_circuit)	C++17	25 / 100	1067 ms	13336 KiB

circuit

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod=1000002022;
vector<int>ch[200009];
int sz[200009], f[200009],n,m;
void dfs(int x)
{
    if(ch[x].empty()){sz[x]=1;return;}
    sz[x]=ch[x].size();
    for(int i=0;i<ch[x].size();i++){dfs(ch[x][i]);sz[x]=(sz[x]*1LL*sz[ch[x][i]])%mod;}
   // cout<<55<<" "<<x<<" "<<sz[x]<<endl;
}
int suf[200009];
void go(int x,int prd)
{
    //cout<<66<<" "<<x<<" "<<prd<<endl;
    if(ch[x].empty()){f[x-n]=prd;return;}
    int w=ch[x].size();
    suf[w]=1;
    for(int i=w-1;i>=0;i--)suf[i]=(suf[i+1]*1LL*sz[ch[x][i]])%mod;
    int d=1;
    for(int i=0;i<w;i++)
    {
        int r=(d*1LL*suf[i+1])%mod;
        go(ch[x][i],(r*1LL*prd)%mod);
        d=(d*1LL*sz[ch[x][i]])%mod;
    }
}
int sg[40009][2];
int lz[400009];
vector<int>onn;
void build(int x=1,int st=0,int en=m-1)
{
    if(st==en){sg[x][0]=f[st];sg[x][1]=f[st]*onn[st];return;}
    int mid=(st+en)>>1;
    build((x<<1),st,mid);
    build((x<<1)|1,mid+1,en);
    sg[x][0]=(sg[(x<<1)][0]+sg[(x<<1)|1][0])%mod;
    sg[x][1]=(sg[(x<<1)][1]+sg[(x<<1)|1][1])%mod;


}
void psh(int x,int st,int en)
{
    if(lz[x]==0)return;
    sg[x][1]=(sg[x][0]-sg[x][1]+mod)%mod;
    lz[x]=0;
    if(en>st)
    {
        lz[(x<<1)]=1-lz[(x<<1)];
        lz[(x<<1)|1]=1-lz[(x<<1)|1];

    }
}
void upd(int l,int r,int x=1,int st=0,int en=m-1)
{
    psh(x,st,en);
    if(l>en||st>r)return;
    if(st>=l && en<=r){lz[x]=1;psh(x,st,en);return ;}
    int mid=(st+en)>>1;
    upd(l,r,(x<<1),st,mid);
    upd(l,r,(x<<1)|1,mid+1,en);
    sg[x][0]=(sg[(x<<1)][0]+sg[(x<<1)|1][0])%mod;
    sg[x][1]=(sg[(x<<1)][1]+sg[(x<<1)|1][1])%mod;

}
void init(int N,int M,vector<int> P,vector<int> A)
{
    n=N;
    m=M;
    onn=A;
    for(int i=1;i<n+m;i++)
        ch[P[i]].push_back(i);
    dfs(0);
    go(0,1);
    build();
    /*for(int i=0;i<m;i++)cout<<f[i]<<" ";
    cout<<endl;

    cout<<sg[1][0]<<" "<<sg[1][1]<<endl;*/
}
int count_ways(int L,int R)
{
    upd(L-n,R-n);
    return sg[1][1];
}

Compilation message (stderr)

circuit.cpp: In function 'void dfs(int)':
circuit.cpp:11:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i=0;i<ch[x].size();i++){dfs(ch[x][i]);sz[x]=(sz[x]*1LL*sz[ch[x][i]])%mod;}
      |                 ~^~~~~~~~~~~~~

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