oj.uz

Submission #1078533

# Submission time Handle Problem Language Result Execution time Memory
1078533 2024-08-27T19:39:22 Z ArthuroWich Digital Circuit (IOI22_circuit) C++17
2 / 100
 477 ms 9560 KB 
#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
vector<int> adj[200005];
int v[200005], a[200005], arr[200005], brr[200005], seg1[4*200005], seg0[4*200005], s[4*200005], dep[200005], mod = 1000002022;
void lazypropagate(int n, int l, int r) {
    if (s[n]) {
        swap(seg1[n], seg0[n]);
        if (l != r) {
            s[2*n] ^= 1;
            s[2*n+1] ^= 1;
        }
        s[n] = 0;
    }
}
void build(int n, int l, int r) {
    if (l == r) {
        seg1[n] = arr[l];
        seg0[n] = brr[l];
    } else {
        int m = (l+r)/2;
        build(2*n, l, m);
        build(2*n+1, m+1, r);
        seg1[n] = seg1[2*n] + seg1[2*n+1];
        seg1[n] %= mod;
        seg0[n] = seg0[2*n] + seg0[2*n+1];
        seg0[n] %= mod;
    }
}
void update(int n, int l, int r, int a, int b) {
    lazypropagate(n, l, r);
    if (b < l || r < a) {
        return;
    } else if (a <= l && r <= b) {
        s[n] = 1;
        lazypropagate(n, l, r);
    } else {
        int m = (l+r)/2;
        update(2*n, l, m, a, b);
        update(2*n+1, m+1, r, a, b);
        seg1[n] = seg1[2*n] + seg1[2*n+1];
        seg1[n] %= mod;
        seg0[n] = seg0[2*n] + seg0[2*n+1];
        seg0[n] %= mod;
    }
}
int n, m;
void dfs1(int i) {
    if (adj[i].size() == 0) {
        v[i] = 1;
    } else {
        v[i] = adj[i].size();
    }
    for (int j : adj[i]) {
        dfs1(j);
    }
    for (int j : adj[i]) {
        v[i] *= v[j];
        v[i] %= mod;
    }
}
void dfs2(int i, int va) {
    if (adj[i].size() == 0) {
        a[i] = va;
        return;
    }
    int l = adj[i].size();
    vector<int> pref(l+2, 1), suff(l+2, 1);
    for (int j = 1; j <= l; j++) {
        pref[j] *= v[adj[i][j-1]];
        suff[j] *= v[adj[i][j-1]];
    }
    for (int j = 1; j <= l+1; j++) {
        pref[j] *= pref[j-1];
        pref[j] %= mod;
    }
    for (int j = l; j >= 0; j--) {
        suff[j] *= suff[j+1];
        suff[j] %= mod;
    }
    for (int j = 1; j <= l; j++) {
        int b = pref[j-1]*suff[j+1];
        b %= mod;
        dfs2(adj[i][j-1], b);
    }
}
void init(int32_t N, int32_t M, vector<int32_t> P, vector<int32_t> A) {
    n = N, m = M;
    for (int i = 1; i <= n+m-1; i++) {
        adj[P[i]].push_back(i);
    }
    vector<int> b(n+1, 1);
    for (int i = 1; i <= n; i++) {
        b[i] = b[i-1]*2;
        b[i] %= mod;
    }
    dfs1(0);
    dfs2(0, 1);
    for (int i = 0; i < m; i++) {
        if (A[i]) {
            arr[i] = a[i+n];
        } else {
            brr[i] = a[i+n];
        }
    }
    build(1, 0, m-1);
}
int32_t count_ways(int32_t L, int32_t R) {
    update(1, 0, m-1, L-n, R-n);
    return seg1[1];
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 3 ms 5208 KB Output is correct
4 Correct 3 ms 5208 KB Output is correct
5 Correct 2 ms 5208 KB Output is correct
6 Correct 2 ms 5068 KB Output is correct
7 Correct 2 ms 5208 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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