Submission #932578

#	Time	Username	Problem	Language	Result	Execution time	Memory
932578		velislavgarkov	Digital Circuit (IOI22_circuit)	C++17	100 / 100	714 ms	49264 KiB

circuit

#include "circuit.h"
#include <iostream>
#include <vector>
using namespace std;
const int MAXN=2e5+10;
const long long mod=1e9+2022;
vector <int> v[MAXN];
vector <long long> pref[MAXN], suf[MAXN];
long long mult[MAXN];
long long tree[4*MAXN][2], val[MAXN];
int lazy[4*MAXN];
int start[MAXN];
int n, m;
void precomp(int x) {
    if (v[x].empty()) {
        mult[x]=1;
        return;
    }
    pref[x].resize(v[x].size());
    suf[x].resize(v[x].size());
    mult[x]=v[x].size();
    for (int i=0;i<v[x].size();i++) {
        precomp(v[x][i]);
        if (i==0) pref[x][i]=mult[v[x][i]];
        else pref[x][i]=(pref[x][i-1]*mult[v[x][i]])%mod;
        mult[x]=(mult[x]*mult[v[x][i]])%mod;
    }
    for (int i=v[x].size()-1;i>=0;i--) {
        if (i==v[x].size()-1) suf[x][i]=mult[v[x][i]];
        else suf[x][i]=(suf[x][i+1]*mult[v[x][i]])%mod;
    }
}
void dfs(int x, long long ways) {
    if (x>=n) {
        val[x-n]=ways;
        //cout << x << ' ' << ways << endl;
        return;
    }
    long long s;
    for (int i=0;i<v[x].size();i++) {
        s=1;
        if (i>0) s*=pref[x][i-1];
        if (i<v[x].size()-1) s*=suf[x][i+1];
        s%=mod;
        dfs(v[x][i],(ways*s)%mod);
    }
}
void build_tree(int node, int l, int r) {
    if (l==r) {
        tree[node][0]=tree[node][1]=0;
        tree[node][start[l]]=val[l];
        return;
    }
    int mid=(l+r)/2;
    build_tree(node*2,l,mid);
    build_tree(node*2+1,mid+1,r);
    tree[node][0]=(tree[node*2][0]+tree[node*2+1][0])%mod;
    tree[node][1]=(tree[node*2][1]+tree[node*2+1][1])%mod;
}
void push_lazy(int node, int l, int r) {
    if (l!=r && lazy[node]%2==1) {
        lazy[node*2]++;
        lazy[node*2+1]++;
        swap(tree[node*2][0],tree[node*2][1]);
        swap(tree[node*2+1][0],tree[node*2+1][1]);
    }
    lazy[node]=0;
}
void update(int node, int l, int r, int ql, int qr) {
    if (ql>r || qr<l) return;
    push_lazy(node,l,r);
    if (l>=ql && r<=qr) {
        swap(tree[node][0],tree[node][1]);
        lazy[node]++;
        return;
    }
    int mid=(l+r)/2;
    update(node*2,l,mid,ql,qr);
    update(node*2+1,mid+1,r,ql,qr);
    tree[node][0]=(tree[node*2][0]+tree[node*2+1][0])%mod;
    tree[node][1]=(tree[node*2][1]+tree[node*2+1][1])%mod;
}
void init(int N, int M, vector <int> p, vector <int> a) {
    n=N;
    m=M;
    for (int i=1;i<n+m;i++) v[p[i]].push_back(i);
    for (int i=0;i<m;i++) start[i]=a[i];
    precomp(0);
    dfs(0,1);
    build_tree(1,0,m-1);
}
int count_ways(int l, int r) {
    l-=n; r-=n;
    update(1,0,m-1,l,r);
    return tree[1][1];
}

Compilation message (stderr)

circuit.cpp: In function 'void precomp(int)':
circuit.cpp:22:19: 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<v[x].size();i++) {
      |                  ~^~~~~~~~~~~~
circuit.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         if (i==v[x].size()-1) suf[x][i]=mult[v[x][i]];
      |             ~^~~~~~~~~~~~~~~
circuit.cpp: In function 'void dfs(int, long long int)':
circuit.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i=0;i<v[x].size();i++) {
      |                  ~^~~~~~~~~~~~
circuit.cpp:43:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         if (i<v[x].size()-1) s*=suf[x][i+1];
      |             ~^~~~~~~~~~~~~~

• 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