Submission #627315

#	Time	Username	Problem	Language	Result	Execution time	Memory
627315		jeroenodb	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1562 ms	15556 KiB

circuit

#include "circuit.h"

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const long long MD = 1e9+2022;
template<long long MOD=MD> struct mdint {
    int d=0;
    mdint () {d=0;}
    mdint (long long _d) : d(_d%MOD){
        if(d<0) d+=MOD;
    };
    friend mdint& operator+=(mdint& a, const mdint& o) {
        a.d+=o.d; if(a.d>=MOD) a.d-=MOD;
        return a;
    }
    friend mdint& operator-=(mdint& a, const mdint& o) {
        a.d-=o.d; if(a.d<0) a.d+=MOD;
        return a;
    }
    friend mdint& operator*=(mdint& a, const mdint& o) {
        return a = mdint((ll)a.d*o.d);
    }
    mdint operator*(const mdint& o) const {
        mdint res = *this;
        res*=o;
        return res;
    }
    mdint operator+(const mdint& o) const {
        mdint res = *this;
        res+=o;
        return res;
    }
    mdint operator-(const mdint& o) const {
        mdint res = *this;
        res-=o;
        return res;
    }
    mdint operator^(long long b) const {
        mdint tmp = 1;
        mdint power = *this;
        while(b) {
            if(b&1) {
                tmp = tmp*power;
            }
            power = power*power;
            b/=2;
        }
        return tmp;
    }
    bool operator==(const mdint& o) { return d==o.d;}
    bool operator!=(const mdint& o) { return d!=o.d;}
    friend istream& operator>>(istream& c, mdint& a) {return c >> a.d;}
    friend ostream& operator<<(ostream& c, const mdint& a) {return c << a.d;}
};
using  mint = mdint<MD>;
struct segtree {
    struct node {
        mint res[2] = {};
        bool flip=0;
        node() {}
    };
    vector<node> seg;
    int n,ptwo;
    segtree() {}
    segtree(int nn) {
        n=nn,ptwo=1;
        while(ptwo<n) ptwo*=2;
        seg.resize(2*ptwo);
    }
    void puttag(int i, bool f) {
        auto& v = seg[i];
        if(f) {
            swap(v.res[0],v.res[1]);
            v.flip^=1;
        }
    }
    void pull(int i) {
        auto& v = seg[i];
        v.res[0] = seg[i*2].res[0]+seg[i*2+1].res[0];
        v.res[1] = seg[i*2].res[1]+seg[i*2+1].res[1];
    }
    void push(int i) { // TODO!
        auto& v = seg[i];
        if(v.flip) {
            puttag(i*2,v.flip);
            puttag(i*2+1,v.flip);
        }
        v.flip=false;
    }
    void set(int i, int l, int r, int ql, int qr) {
        if(qr<l or r<ql) return;
        if(ql<=l and r<=qr) {
            puttag(i,1); // correct?
            return;
        }
        int mid = (l+r)/2;
        push(i);
        set(i*2,l,mid,ql,qr),set(i*2+1,mid+1,r,ql,qr);
        pull(i);
    }
    void set(int l, int r) {
        set(1,0,ptwo-1,l,r);
    }
    node& operator[](int i) {return seg[i+ptwo];}
    void build() {
        for(int i=ptwo-1;i>=1;--i) {
            pull(i);
        }
    }
};

segtree seg;
int n;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n=N;
    vvi adj(N+M);
    for(int i=1;i<N+M;++i) {
        adj[P[i]].push_back(i);
    }
    vector<mint> degProd(N+M,1);
    for(int i=N-1;i>=0;--i) {
        degProd[i]=adj[i].size();
        for(int to : adj[i]) {
            degProd[i]*=degProd[to];
        }
    }
    vector<mint> w(N+M,1);
    for(int i=0;i<N;++i) {
       
        int c = adj[i].size();
        vector<mint> pref(c+1,1);
        for(int j=1;j<=c;++j) {
            pref[j]=pref[j-1]*degProd[adj[i][j-1]];
        }
        mint suf=1;
        for(int j=c-1;j>=0;--j) {
            w[adj[i][j]]=w[i]*pref[j]*suf;
            suf*=degProd[adj[i][j]];
        }
    }
    seg = segtree(M);
    for(int i=0;i<M;++i) {
        seg[i].res[A[i]] = w[i+N];
    }
    seg.build();
}

int count_ways(int L, int R) {
    seg.set(L-n,R-n);
    return seg.seg[1].res[1].d;
}

• 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