Submission #642961

#	Time	Username	Problem	Language	Result	Execution time	Memory
642961		Pajaraja	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1077 ms	45952 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#include <vector>
#define MAXN 200007
#define MOD 1000002022
using namespace std;
vector<int> g[MAXN];
long long a[MAXN],t[MAXN],seg[2][4*MAXN];
int n,m,p[MAXN],st[MAXN],bag[4*MAXN];
void dfst(int s)
{
    for(int i=0;i<g[s].size();i++) dfst(g[s][i]);
    if(g[s].size()==0) t[s]=1;
    else t[s]=g[s].size();
    for(int i=0;i<g[s].size();i++) t[s]=(t[s]*t[g[s][i]])%MOD;
}
void dfs(int s,long long p)
{
    if(s>=n) {a[s-n]=p%MOD; return;}
    vector<long long> lv(g[s].size()+7),ds(g[s].size()+7);
    ds[0]=1; lv[g[s].size()+1]=1;
    for(int i=0;i<g[s].size();i++) ds[i+1]=(ds[i]*t[g[s][i]])%MOD;
    for(int i=g[s].size()-1;i>=0;i--) lv[i+1]=(lv[i+2]*t[g[s][i]])%MOD;
    for(int i=0;i<g[s].size();i++) dfs(g[s][i],(p*((ds[i]*lv[i+2])%MOD))%MOD);
}
void build(int l,int r,int ind)
{
    if(l==r) {seg[st[l]][ind]=a[l]; return;}
    int s=(l+r)/2;
    build(l,s,2*ind);
    build(s+1,r,2*ind+1);
    for(int k=0;k<2;k++) seg[k][ind]=(seg[k][2*ind]+seg[k][2*ind+1])%MOD;
}
void relax(int ind)
{
    bag[2*ind]^=bag[ind]; bag[2*ind+1]^=bag[ind];
    bag[ind]=0;
}
void upd(int lt,int rt,int l,int r,int ind)
{
    if(r<lt || l>rt) return;
    if(l>=lt && r<=rt) {bag[ind]^=1; return;}
    relax(ind);
    int s=(l+r)/2;
    upd(lt,rt,l,s,2*ind);
    upd(lt,rt,s+1,r,2*ind+1);
    for(int k=0;k<2;k++) seg[k][ind]=(seg[k^bag[2*ind]][2*ind]+seg[k^bag[2*ind+1]][2*ind+1])%MOD;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n=N; m=M;
    for(int i=1;i<N+M;i++) g[P[i]].push_back(i);
    for(int i=0;i<M;i++) st[i]=A[i];
    dfst(0); dfs(0,1);
    build(0,m-1,1);
}

int count_ways(int L, int R) {
    upd(L-n,R-n,0,m-1,1);
    return seg[1^bag[1]][1];
}

Compilation message (stderr)

circuit.cpp: In function 'void dfst(int)':
circuit.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0;i<g[s].size();i++) dfst(g[s][i]);
      |                 ~^~~~~~~~~~~~
circuit.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=0;i<g[s].size();i++) t[s]=(t[s]*t[g[s][i]])%MOD;
      |                 ~^~~~~~~~~~~~
circuit.cpp: In function 'void dfs(int, long long int)':
circuit.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<g[s].size();i++) ds[i+1]=(ds[i]*t[g[s][i]])%MOD;
      |                 ~^~~~~~~~~~~~
circuit.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<g[s].size();i++) dfs(g[s][i],(p*((ds[i]*lv[i+2])%MOD))%MOD);
      |                 ~^~~~~~~~~~~~

• 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