Submission #819061

#	Time	Username	Problem	Language	Result	Execution time	Memory
819061		andrei_boaca	Digital Circuit (IOI22_circuit)	C++17	100 / 100	988 ms	43008 KiB

circuit

#include "circuit.h"

#include <vector>
#include <bits/stdc++.h>
//#include "stub.cpp"
using namespace std;
typedef long long ll;
const ll mod=1e9+2022;
ll n,m,par[200005];
vector<ll> muchii[200005];
ll val[200005];
ll sub[200005],coef[200005];
void dfs(int nod)
{
    sub[nod]=1;
    if(muchii[nod].empty())
        return;
    sub[nod]*=(ll)muchii[nod].size();
    sub[nod]%=mod;
    for(int i:muchii[nod])
    {
        dfs(i);
        sub[nod]=(sub[nod]*sub[i])%mod;
    }
}
void calc(int nod,ll c)
{
    if(muchii[nod].empty())
    {
        coef[nod-n+1]=c;
        return;
    }
    vector<ll> pref;
    vector<ll> suf;
    ll prod=1;
    for(int i=0;i<muchii[nod].size();i++)
    {
        prod=(prod*sub[muchii[nod][i]])%mod;
        pref.push_back(prod);
    }
    prod=1;
    for(int i=(int)muchii[nod].size()-1;i>=0;i--)
    {
        prod=(prod*sub[muchii[nod][i]])%mod;
        suf.push_back(prod);
    }
    reverse(suf.begin(),suf.end());
    for(int i=0;i<muchii[nod].size();i++)
    {
        ll val=1;
        if(i>0)
            val=(val*pref[i-1])%mod;
        if(i+1<muchii[nod].size())
            val=(val*suf[i+1])%mod;
        val=(val*c)%mod;
        calc(muchii[nod][i],val);
    }
}
ll arb[2][8*100005],toprop[8*100005];
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        arb[0][nod]=(val[st]==0)*coef[st];
        arb[1][nod]=(val[st]==1)*coef[st];
        return;
    }
    ll mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    arb[0][nod]=(arb[0][nod*2]+arb[0][nod*2+1])%mod;
    arb[1][nod]=(arb[1][nod*2]+arb[1][nod*2+1])%mod;
}
void prop(int nod)
{
    toprop[nod*2]^=1;
    toprop[nod*2+1]^=1;
    swap(arb[0][nod*2],arb[1][nod*2]);
    swap(arb[0][nod*2+1],arb[1][nod*2+1]);
}
void update(int nod,int st,int dr,int a,int b)
{
    if(st!=dr&&toprop[nod])
        prop(nod);
    toprop[nod]=0;
    if(st>=a&&dr<=b)
    {
        swap(arb[0][nod],arb[1][nod]);
        toprop[nod]=1;
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        update(nod*2,st,mij,a,b);
    if(b>mij)
        update(nod*2+1,mij+1,dr,a,b);
    arb[0][nod]=(arb[0][nod*2]+arb[0][nod*2+1])%mod;
    arb[1][nod]=(arb[1][nod*2]+arb[1][nod*2+1])%mod;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n=N;
    m=M;
    for(int i=0;i<P.size();i++)
    {
        muchii[P[i]].push_back(i);
        par[i]=P[i];
    }
    for(int i=0;i<A.size();i++)
        val[i+1]=A[i];
    dfs(0);
    calc(0,1);
    build(1,1,m);
}

int count_ways(int L, int R) {
    L-=n;
    R-=n;
    L++;
    R++;
    update(1,1,m,L,R);
    return arb[1][1];
}

Compilation message (stderr)

circuit.cpp: In function 'void calc(int, ll)':
circuit.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<muchii[nod].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
circuit.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i=0;i<muchii[nod].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
circuit.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         if(i+1<muchii[nod].size())
      |            ~~~^~~~~~~~~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i=0;i<P.size();i++)
      |                 ~^~~~~~~~~
circuit.cpp:108:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int i=0;i<A.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