Submission #1079653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079653		kl0989e	Digital Circuit (IOI22_circuit)	C++17	100 / 100	820 ms	39856 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=2e5+10;
const int maxm=1e5+10;
const int mod=1000002022;

int n,m;
vector<vi> graph(maxn);
vl mul(maxn,1);
vl vals(maxm,0);

void dfs(int cur) {
    mul[cur]=max(1,(int)graph[cur].size());
    for (auto to:graph[cur]) {
        dfs(to);
        mul[cur]=(mul[cur]*mul[to])%mod;
    }
}

void dfs2(int cur, ll mult=1) {
    if (graph[cur].size()==0) {
        vals[cur-n]=mult;
        return;
    }
    vl pref(graph[cur].size()+1,1),suff(graph[cur].size()+1,1);
    for (int i=0; i<graph[cur].size(); i++) {
        pref[i+1]=mul[graph[cur][i]]*pref[i]%mod;
        suff[graph[cur].size()-i-1]=mul[graph[cur][graph[cur].size()-i-1]]*suff[graph[cur].size()-i]%mod;
    }
    for (int i=0; i<graph[cur].size(); i++) {
        dfs2(graph[cur][i],(mult*pref[i]%mod)*suff[i+1]%mod);
    }
}

struct SegTree {
    struct Node {
        ll sum=0,actsum=0;
        bool flip=0;

        Node(ll _sum=0, ll _actsum=0): sum(_sum),actsum(_actsum) {}
    };

    Node unite(Node a, Node b) {
        return {(a.sum+b.sum)%mod,(a.actsum+b.actsum)%mod};
    }

    vector<Node> tree;
    int sze;

    void push(int v, int tl, int tr) {
        if (tree[v].flip) {
            tree[v].actsum=(tree[v].sum-tree[v].actsum+mod)%mod;
            if (tl!=tr) {
                tree[v*2].flip^=1;
                tree[v*2+1].flip^=1;
            }
            tree[v].flip=0;
        }
    }

    void init(int _sze, vl& vals, vi& onoff) {
        sze=_sze;
        tree.resize(4*sze);
        build(vals,onoff,1,0,sze-1);
    }

    void build(vl& vals, vi& onoff, int v, int tl, int tr) {
        if (tl==tr) {
            if (onoff[tl]) {
                tree[v]={vals[tl],vals[tl]};
            }
            else {
                tree[v]={vals[tl],0};
            }
            return;
        }
        int tm=tl+(tr-tl)/2;
        build(vals,onoff,v*2,tl,tm);
        build(vals,onoff,v*2+1,tm+1,tr);
        tree[v]=unite(tree[v*2],tree[v*2+1]);
    }

    void flip(int l, int r, int v, int tl, int tr) {
        push(v,tl,tr);
        if (r<tl || l>tr) {
            return;
        }
        if (l<=tl && tr<=r) {
            tree[v].flip=1;
            push(v,tl,tr);
            return;
        }
        int tm=tl+(tr-tl)/2;
        flip(l,r,v*2,tl,tm);
        flip(l,r,v*2+1,tm+1,tr);
        tree[v]=unite(tree[v*2],tree[v*2+1]);
    }
    void flip(int l, int r) {
        flip(l,r,1,0,sze-1);
    }

    ll get() {
        return tree[1].actsum;
    }
};

SegTree dat;

void init(int nn, int mm, vi parent, vi onoff) {
    n=nn;
    m=mm;
    for (int i=1; i<n+m; i++) {
        graph[parent[i]].pb(i);
    }
    dfs(0);
    dfs2(0);
    dat.init(m,vals,onoff);
}

int count_ways(int l, int r) {
    dat.flip(l-n,r-n);
    return dat.get();
}

Compilation message (stderr)

circuit.cpp: In function 'void dfs2(int, long long int)':
circuit.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i=0; i<graph[cur].size(); i++) {
      |                   ~^~~~~~~~~~~~~~~~~~
circuit.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i=0; i<graph[cur].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