Submission #831653

#	Time	Username	Problem	Language	Result	Execution time	Memory
831653		Wael	Digital Circuit (IOI22_circuit)	C++17	0 / 100	1412 ms	2097152 KiB

circuit

#include <bits/stdc++.h>
using namespace std;
#include "circuit.h"
#define F first
#define S second
typedef int ll;
int const Mx = 1e6 + 10 , mod = 1000002022;
int n , m , N , M , state[Mx] , ways[Mx][3] , segmentTree = 1 , mn[Mx] , Left[Mx] , Right[Mx] , op[Mx];
vector<ll>adj[Mx];

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;
}

inline bool cmp(int a , int b) {
    return mn[a] < mn[b];
}

inline void Order(int node) {

    mn[node] = 1e9;
    for(auto next : adj[node]) {
        Order(next);
        mn[node] = min(mn[node] , mn[next]);
    }
    sort(adj[node].begin() , adj[node].end() , cmp);
    if(node >= N) mn[node] = node;

}

inline void calc(int node) {
    ways[node][1] = ways[node][0] = 0;
    vector<ll>Dp;
    Dp.assign(adj[node].size() + 2 , 0);
    Dp[0] = 1;
    for(int i = 0 ; i < adj[node].size() ; ++i) {
        int next = adj[node][i];
        for(int cnt = i + 1 ; cnt >= 0 ; --cnt) {
            //cout << "cnt = " << cnt << endl;
            Dp[cnt] = Add(Mul(Dp[cnt] , ways[next][0]) , cnt > 0 ? (Mul(Dp[cnt - 1] , ways[next][1])) : 0 );
        }
    }

    for(int cnt = 0 ; cnt <= adj[node].size() ; ++cnt) { 
        ways[node][1] = Add(ways[node][1] , Mul(Dp[cnt] , cnt));
        ways[node][0] = Add(ways[node][0] , Mul(Dp[cnt] , (adj[node].size() - cnt)));
    }
}

inline void Build(int node = 0) {
    if(node >= N) {
        if(state[node] == 1) ways[node][1] = 1;
        else ways[node][1] = 0;
        ways[node][0] = 1 - ways[node][1];
        return;
    }

    Build(Left[node]);
    Build(Right[node]);

    calc(node);
}

void init(int X , int Y , vector<int> P, vector<int> A) {
    N = X , M = Y;
    if(M & (M - 1) != 0) segmentTree = 0;
    if(M != N + 1) segmentTree = 0;
    for(int i = 1 ; i < P.size() ; ++i) {
        adj[P[i]].push_back(i);
        if(P[i] != (i - 1) / 2) segmentTree = 0;
    }
    for(int i = 0 ; i < A.size() ; ++i) state[i + N] = A[i];
    if(segmentTree) {
        Order(0);
        for(int node = 0 ; node < N ; ++node) {
            Left[node] = adj[node][0];
            Right[node] = adj[node][1];
        }
        Build();
    }
}

inline void Dfs(int node) { //cout << "node = " << node << endl;

    for(auto next : adj[node]) Dfs(next);

    if(node >= N) {
        if(state[node] == 1) ways[node][1] = 1;
        else ways[node][1] = 0;
        ways[node][0] = 1 - ways[node][1];
        return;
    }

    calc(node);
    return;

}

inline void Push(int node) {
    if(op[node] == 0) return;
    op[Left[node]] ^= 1;
    op[Right[node]] ^= 1;
    op[node] = 0;
    swap(ways[Left[node]][1] , ways[Left[node]][0]);
    swap(ways[Right[node]][1] , ways[Right[node]][0]);
    return;
}

inline void Update(int l , int r , int node = 0 , int lx = 1 , int rx = M) {
    if(lx > r && rx < l) return;
    if(lx >= l && rx <= r) {
        op[node] ^= 1;
        swap(ways[node][1] , ways[node][0]);
        return;
    }
    Push(node);
    int mid = (lx + rx) / 2;
    Update(l , r , Left[node] , lx , mid);
    Update(l , r , Right[node] , mid + 1 , rx);
    calc(node);
}
int count_ways(int L, int R) {
    if(segmentTree) {
        Update(L - N + 1 , R - N + 1);
        return ways[0][1];
    }
    for(int i = L ; i <= R ; ++i) state[i] = !state[i];
    Dfs(0);
    return ways[0][1];
}

Compilation message (stderr)

circuit.cpp: In function 'void calc(int)':
circuit.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0 ; i < adj[node].size() ; ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~~
circuit.cpp:52:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int cnt = 0 ; cnt <= adj[node].size() ; ++cnt) {
      |                       ~~~~^~~~~~~~~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:74:20: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   74 |     if(M & (M - 1) != 0) segmentTree = 0;
      |            ~~~~~~~~^~~~
circuit.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 1 ; i < P.size() ; ++i) {
      |                     ~~^~~~~~~~~~
circuit.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i = 0 ; i < A.size() ; ++i) state[i + N] = A[i];
      |                     ~~^~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11