Submission #835779

#	Time	Username	Problem	Language	Result	Execution time	Memory
835779		Wael	Digital Circuit (IOI22_circuit)	C++17	100 / 100	973 ms	54724 KiB

circuit

#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
typedef int ll;
int const Mx = 1e6 + 10;
int n , m , state[Mx] , mod = 1000002022 , dp[Mx] , Size = 1 , val[Mx];
vector<long long>adj[Mx] , off , on , op;

inline long long Mul(long long x , long long y) {
    x %= mod;
    y %= mod;
    return (x * y) % mod;
}

inline long long Add(long long x , long long y) {
    x %= mod;
    y %= mod;
    return (x + y) % mod;
}

struct sgtree {

    inline void Init(int n) {
        while(Size < n) Size *= 2;
        on.assign(Size * 2 , 0);
        off.assign(Size * 2 , 0);
        op.assign(Size * 2 , 0);
    }

    inline void Build(int x = 1 , int lx = 1 , int rx = Size) {
        if(lx == rx) {
            off[x] = val[lx];
            return;
        }
        int mid = (lx + rx) / 2;
        Build(2 * x , lx , mid);
        Build(2 * x + 1 , mid + 1 , rx);
        off[x] = off[2 * x] + off[2 * x + 1];
    }

    inline void Push(int x) {
        if(op[x] == 0) return;
        op[x] = 0;
        op[2 * x] ^= 1;
        op[2 * x + 1] ^= 1;
        swap(off[2 * x] , on[2 * x]);
        swap(off[2 * x + 1] , on[2 * x + 1]);
    }

    inline void Update(int l , int r , int x = 1 , int lx = 1 , int rx = Size) {
        if(lx > r || rx < l) return;
        if(lx >= l && rx <= r) {
            swap(off[x] , on[x]);
            op[x] ^= 1;
            return;
        }
        Push(x);
        int mid = (lx + rx) / 2;
        Update(l , r , 2 * x , lx , mid);
        Update(l , r , 2 * x + 1 , mid + 1 , rx);
        off[x] = off[2 * x] + off[2 * x + 1];
        on[x] = on[2 * x] + on[2 * x + 1];
    }

}st;

inline void DfsDp(int node) {
    dp[node] = 1;
    for(auto next : adj[node]) {
        DfsDp(next);
        dp[node] = Mul(dp[node] , dp[next]);
    }
    if(adj[node].size()) dp[node] = Mul(dp[node] , adj[node].size());
}

inline void GetVal(int node , int res = 1) {
    if(node >= n) {
        val[node - n + 1] = res;
        return;
    }
    vector<ll>pref , suf;
    for(int i = 0 ; i < adj[node].size() ; ++i) {
        int cur = 1 , next = adj[node][i];
        if(pref.size()) cur = pref.back();
        cur = Mul(cur , dp[next]);
        pref.push_back(cur);
    }

    for(int i = adj[node].size() - 1 ; i >= 0 ; --i) {
        int cur = 1 , next = adj[node][i];
        if(suf.size()) cur = suf.back();
        cur = Mul(cur , dp[next]);
        suf.push_back(cur);
    }

    for(int i = 0 ; i < adj[node].size() ; ++i) {
        int CurRes = res , next = adj[node][i];
        if(i) CurRes = Mul(CurRes , pref[i - 1]);
        if((int)adj[node].size() - i - 2 >= 0) CurRes = Mul(CurRes , suf[adj[node].size() - 2 - i]);
        GetVal(next , CurRes);
    }
}

void init(int N, int M, vector<ll> P, vector<ll> A) {
    n = N , m = M;
    for(int i = 1 ; i < P.size() ; ++i) adj[P[i]].push_back(i);
    for(int i = 0 ; i < A.size() ; ++i) state[i + 1] = A[i];
    DfsDp(0);
    GetVal(0);
    st.Init(m);
    st.Build();
    //for(int i = 1 ; i <= m ; ++i) cout << val[i] << " " ;
    //cout << endl;
    for(int i = 1 ; i <= m ; ++i) if(state[i]) st.Update(i , i);
}

int count_ways(int L , int R) {
    L -= n , ++L;
    R -= n , ++R;
    st.Update(L , R);
    return on[1] % mod;
}

Compilation message (stderr)

circuit.cpp: In function 'void GetVal(int, int)':
circuit.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i = 0 ; i < adj[node].size() ; ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~~
circuit.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i = 0 ; i < adj[node].size() ; ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i = 1 ; i < P.size() ; ++i) adj[P[i]].push_back(i);
      |                     ~~^~~~~~~~~~
circuit.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0 ; i < A.size() ; ++i) state[i + 1] = A[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