Submission #722241

#	Time	Username	Problem	Language	Result	Execution time	Memory
722241		bin9638	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1321 ms	45424 KiB

circuit

#include <bits/stdc++.h>

#ifndef SKY
#include "circuit.h"
#endif // SKY

using namespace std;

#define N 500010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

int n,times;
vector<int>g[N];
ii cnt[N];
ll f[N],dp[N];

const ll mod=1000002022;

void selfmull(ll&u,ll v)
{
    v%=mod;
    u=u*v%mod;
}

struct IT_nhan
{
    ll ST[N*4]={};

    void init(int n)
    {
        for(int i=1;i<=n*4;i++)
            ST[i]=1;
    }

    void update(int id,int l,int r,int u,int v,ll val)
    {
        if(l>v||r<u)
            return;
      //  cout<<l<<" "<<r<<" "<<u<<" "<<v<<" "<<val<<endl;
        if(l>=u&&r<=v)
        {
            selfmull(ST[id],val);
            return;
        }
        int mid=(l+r)/2;
        update(id*2,l,mid,u,v,val);
        update(id*2+1,mid+1,r,u,v,val);
    }

    ll get(int id,int l,int r,int i)
    {
        //cout<<id<<" "<<l<<" "<<r<<" "<<i<<endl;
        if(l>i||r<i)
            return 1;
        ll res=ST[id];
        if(l==r)
            return res;
        int mid=(l+r)/2;
        selfmull(res,get(id*2,l,mid,i));
        selfmull(res,get(id*2+1,mid+1,r,i));
        return res;
    }
}nhan;

struct IT_cong
{
    struct node
    {
        ll sum=0,val=0;
        int t=0;
    }ST[N*4];

    void down(int id)
    {
        if(ST[id].t==0)
            return;
        ST[id*2].t^=1;
        ST[id*2+1].t^=1;
        ST[id*2].val=(ST[id*2].sum-ST[id*2].val);
        ST[id*2+1].val=(ST[id*2+1].sum-ST[id*2+1].val);
        ST[id].t=0;
    }

    void update(int id,int l,int r,int i,ll val)
    {
        if(l>i||r<i)
            return;
        if(l==r)
        {
        //    cout<<i<<" "<<val<<endl;
            ST[id].sum=val;
            return;
        }
        int mid=(l+r)/2;
        update(id*2,l,mid,i,val);
        update(id*2+1,mid+1,r,i,val);
        ST[id].sum=ST[id*2].sum+ST[id*2+1].sum;
    }

    void flip(int id,int l,int r,int u,int v)
    {
        if(l>v||r<u)
            return;
       // cout<<l<<" "<<r<<" "<<u<<" "<<v<<endl;
        if(l>=u&&r<=v)
        {
            ST[id].val=(ST[id].sum-ST[id].val);
            ST[id].t^=1;
            //cout<<ST[id].val<<endl;
            return;
        }
        down(id);
        int mid=(l+r)/2;
        flip(id*2,l,mid,u,v);
        flip(id*2+1,mid+1,r,u,v);
        ST[id].val=ST[id*2].val+ST[id*2+1].val;
    }
}cong;

void DFS(int u)
{
    f[u]=max(1,(int)g[u].size());
    cnt[u].fs=++times;
    for(auto v:g[u])
    {
        DFS(v);
        selfmull(f[u],f[v]);
    }
    cnt[u].sc=times;
    ll S=1;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        nhan.update(1,1,n,cnt[v].fs,cnt[v].sc,S);
        selfmull(S,f[v]);
    }
    S=1;
    for(int i=g[u].size()-1;i>=0;i--)
    {
        int v=g[u][i];
        nhan.update(1,1,n,cnt[v].fs,cnt[v].sc,S);
        selfmull(S,f[v]);
    }
}

void init(int NNN, int MMM, vector<int> P, vector<int> A)
{
    n=NNN+MMM;
    for(int i=1;i<n;i++)
        g[P[i]].pb(i);
    nhan.init(n);
    DFS(0);
    for(int i=NNN;i<n;i++)
    {
        dp[i]=nhan.get(1,1,n,cnt[i].fs);
       // cout<<i<<" "<<dp[i]<<endl;
       cong.update(1,1,n,i+1,dp[i]);
    }
    for(int i=0;i<MMM;i++)
        if(A[i]==1)
            cong.flip(1,1,n,NNN+i+1,NNN+i+1);
}

int count_ways(int L, int R)
{
    cong.flip(1,1,n,L+1,R+1);
    return (cong.ST[1].val%mod+mod*mod)%mod;
}


#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m;
    cin>>n>>m;
    vector<int>P(n+m),A(m);
    for(int i=0;i<n+m;i++)
        cin>>P[i];
    for(int i=0;i<m;i++)
        cin>>A[i];
    init(n,m,P,A);
    int q;
    cin>>q;
    while(q--)
    {
        int L,R;
        cin>>L>>R;
        cout<<count_ways(L,R)<<endl;
    }
    return 0;
}
#endif

Compilation message (stderr)

circuit.cpp: In function 'void DFS(int)':
circuit.cpp:135:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for(int i=0;i<g[u].size();i++)
      |                 ~^~~~~~~~~~~~

• 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