oj.uz

Submission #835743

# Submission time Handle Problem Language Result Execution time Memory
835743 2023-08-23T19:04:51 Z Wael Digital Circuit (IOI22_circuit) C++17
4 / 100
 823 ms 29980 KB 
#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<ll>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] = Add(off[2 * x] , off[2 * x + 1]);
    }

    inline void Push(int x) {
        if(op[x] == 0) return;
        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] = Add(off[2 * x] , off[2 * x + 1]);
        on[x] = Add(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];
}

Compilation message

circuit.cpp: In function 'void GetVal(int, int)':
circuit.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     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<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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23760 KB Output is correct
2 Correct 11 ms 23760 KB Output is correct
3 Incorrect 14 ms 23760 KB 5th lines differ - on the 1st token, expected: '481', found: '491'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23760 KB Output is correct
2 Correct 12 ms 23760 KB Output is correct
3 Incorrect 12 ms 23736 KB 5th lines differ - on the 1st token, expected: '70832346', found: '563623630'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23760 KB Output is correct
2 Correct 11 ms 23760 KB Output is correct
3 Incorrect 14 ms 23760 KB 5th lines differ - on the 1st token, expected: '481', found: '491'
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 26900 KB Output is correct
2 Correct 823 ms 29968 KB Output is correct
3 Correct 707 ms 29980 KB Output is correct
4 Correct 761 ms 29932 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 26900 KB Output is correct
2 Correct 823 ms 29968 KB Output is correct
3 Correct 707 ms 29980 KB Output is correct
4 Correct 761 ms 29932 KB Output is correct
5 Incorrect 759 ms 26900 KB 5th lines differ - on the 1st token, expected: '882566410', found: '40177750'
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23760 KB Output is correct
2 Correct 12 ms 23760 KB Output is correct
3 Incorrect 12 ms 23736 KB 5th lines differ - on the 1st token, expected: '70832346', found: '563623630'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23760 KB Output is correct
2 Correct 11 ms 23760 KB Output is correct
3 Incorrect 14 ms 23760 KB 5th lines differ - on the 1st token, expected: '481', found: '491'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23760 KB Output is correct
2 Correct 11 ms 23760 KB Output is correct
3 Incorrect 14 ms 23760 KB 5th lines differ - on the 1st token, expected: '481', found: '491'
4 Halted 0 ms 0 KB -