oj.uz

Submission #838342

# Submission time Handle Problem Language Result Execution time Memory
838342 2023-08-26T16:13:42 Z fatemetmhr Digital Circuit (IOI22_circuit) C++17
2 / 100
 460 ms 8332 KB 
// Be name khoda //


#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)   x.begin(), x.end()
#define pb       push_back
#define mp       make_pair
#define fi       first
#define se       second

typedef long long ll;

const int mod   = 1000002022;
const int maxn5 = 2e5 + 10;
const int maxnt = 1e6 + 10;

vector <int> adj[maxn5];
int n, m;
ll val[maxn5], all[maxn5];

void fix(int &a){
    if(a >= mod)
        a -= mod;
}

namespace seg{

    int sum[maxnt][2];
    bool lazy[maxnt];

    void toggle(int l, int r, int lq, int rq, int v){
        if(rq <= l || r <= lq)
            return;
        if(lq <= l && r <= rq){
            lazy[v] ^= 1;
            swap(sum[v][0], sum[v][1]);
            return;
        }
        int mid = (l + r) >> 1;
        toggle(l, mid, lq, rq, v * 2);
        toggle(mid, r, lq, rq, v * 2 + 1);
        fix(sum[v][0] = sum[v * 2][0] + sum[v * 2 + 1][0]);
        fix(sum[v][1] = sum[v * 2][1] + sum[v * 2 + 1][1]);
        if(lazy[v])
            swap(sum[v][0], sum[v][1]);
        return;
        debug(l);
        debug(r);
        debug(lq);
        debug(rq);
        debug(sum[v][0]);
        debug(sum[v][1]);
        debug(lazy[v]);
        debug(sum[v * 2 + 1][0]);
    }

    void build(int l, int r, int v){
        if(r - l == 1){
            sum[v][0] = 0;
            sum[v][1] = val[l + n];
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, v * 2);
        build(mid, r, v * 2 + 1);
        fix(sum[v][0] = sum[v * 2][0] + sum[v * 2 + 1][0]);
        fix(sum[v][1] = sum[v * 2][1] + sum[v * 2 + 1][1]);
    }
}

void dfs2(int v){
    ll x = val[v];
    for(auto u : adj[v]){
        val[u] = x;
        x = x * all[u] % mod;
    }
    x = val[v];
    reverse(all(adj[v]));
    for(auto u : adj[v]){
        val[u] = val[u] * x % mod;
        dfs2(u);
        x = x * all[u] % mod;
    }
    return;
    debug(v);
    debug(all[v]);
    debug(val[v]);
    debug(val[6]);
}

void dfs1(int v){
    all[v] = max(1, int(adj[v].size()));
    for(auto u : adj[v]){
        dfs1(u);
        all[v] = all[v] * all[u] % mod;
    }

}

void init(int N, int M, std::vector<int> p, std::vector<int> a) {
    n = N;
    m = M;
    for(int i = 1; i < n + m; i++)
        adj[p[i]].pb(i);
    val[0] = 1;
    dfs1(0);
    dfs2(0);
    seg::build(0, m, 1);
    for(int i = 0; i < m; i++){
        //debug(i);
        //debug(val[i + n]);
        if(a[i])
            seg::toggle(0, m, i, i + 1, 1);
    }
}

int count_ways(int l, int r) {
    l -= n;
    r -= n;
    seg::toggle(0, m, l, r + 1, 1);
    return seg::sum[1][0];
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 2 ms 5072 KB Output is correct
8 Correct 2 ms 5080 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '52130940', found: '458094764'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 2 ms 5072 KB Output is correct
8 Correct 2 ms 5080 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '52130940', found: '458094764'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 460 ms 8332 KB 1st lines differ - on the 1st token, expected: '431985922', found: '698541100'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 460 ms 8332 KB 1st lines differ - on the 1st token, expected: '431985922', found: '698541100'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '52130940', found: '458094764'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 2 ms 5072 KB Output is correct
8 Correct 2 ms 5080 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '52130940', found: '458094764'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 2 ms 5072 KB Output is correct
8 Correct 2 ms 5080 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '52130940', found: '458094764'
11 Halted 0 ms 0 KB -