Submission #867146

#	Time	Username	Problem	Language	Result	Execution time	Memory
867146		neki	Digital Circuit (IOI22_circuit)	C++17	100 / 100	719 ms	36028 KiB

circuit

#include <bits/stdc++.h>
#define ll long long
#define vc vector

using namespace std;

const ll mod=1000002022, mn=200100;
ll koef[mn], tr[4*mn][2], state[4*mn];
ll N, M;

void update(ll ql, ll qr, ll l, ll r, ll no){
    if(ql==l && qr==r){state[no]=!state[no];}
    else{
        ll mid=(l+r)/2;
        state[no*2]^=state[no];state[no*2+1]^=state[no];
        state[no]=0;
        
        ll ret=0;
        if(qr<=mid) update(ql, qr, l, mid, no*2);
        else if(mid<=ql) update(ql, qr, mid, r, no*2+1);
        else update(ql, mid, l, mid, no*2), update(mid, qr, mid, r, no*2+1);
        
        for(ll i=0;i<2;++i) 
            tr[no][i]=(tr[no*2][state[no*2]^i]+tr[no*2+1][state[no*2+1]^i])%mod;
    }
}


int count_ways(int l, int r){
    update(l-N, r-N+1, 0, M, 1);
    return tr[1][state[1]];
}

void build(ll l, ll r, const vc<int>& a, ll no){
    if(l+1==r) tr[no][!a[l]]=koef[l], state[no]=0;
    else{
        ll mid=(l+r)/2;
        build(l, mid, a, no*2);
        build(mid, r, a, no*2+1);
        
        for(ll i=0;i<2;++i) tr[no][i]=(tr[no*2][i]+tr[no*2+1][i])%mod;
        state[no]=0;
    }
}

void init(int n, int m, vc<int> p, vc<int> a){
    N=n, M=m;
    vc<vc<ll>> edg(n+m);
    for(ll i=n+m-1;i>0;--i)edg[p[i]].push_back(i);
    
    vc<ll> pr(n+m), vse(n+m);
    function<void (ll)> getpros=[&](ll u){
        pr[u]=vse[u]=1;
        if(u>=n);
        else{
            for(auto v: edg[u]){
                getpros(v);
                pr[u]=pr[u]*vse[v]%mod;
            }
            vse[u]=pr[u]*edg[u].size()%mod;
        }
    };
    getpros(0);
    function<void (ll, ll)> getkoef=[&](ll u, ll val){
        if(u>=n) koef[u-n]=val;
        else{
            assert(edg[u].size());
            vc<ll> nv(edg[u].size(),1);
            for(ll i=0,c=1;i<edg[u].size();++i)
                nv[i]=nv[i]*c%mod, c=c*vse[edg[u][i]]%mod;
            for(ll i=(ll)edg[u].size()-1,c=1;i>=0;--i)
                nv[i]=nv[i]*c%mod, c=c*vse[edg[u][i]]%mod;
            //for(ll i=0,c=1;i<edg[u].size();++i)cout<<nv[i]<<" ";cout<<endl;
            for(ll i=0,c=1;i<edg[u].size();++i)
                getkoef(edg[u][i], val*nv[i]%mod);
        }
    };
    
    getkoef(0, 1);
    //for(ll i=0;i<m;++i)cout<<koef[i]<<" ";cout<<endl;
    build(0, M, a, 1);
}

Compilation message (stderr)

circuit.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
circuit.cpp:18:12: warning: unused variable 'ret' [-Wunused-variable]
   18 |         ll ret=0;
      |            ^~~
circuit.cpp: In lambda function:
circuit.cpp:69:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for(ll i=0,c=1;i<edg[u].size();++i)
      |                            ~^~~~~~~~~~~~~~
circuit.cpp:74:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for(ll i=0,c=1;i<edg[u].size();++i)
      |                            ~^~~~~~~~~~~~~~
circuit.cpp:74:24: warning: unused variable 'c' [-Wunused-variable]
   74 |             for(ll i=0,c=1;i<edg[u].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