oj.uz

Submission #763758

# Submission time Handle Problem Language Result Execution time Memory
763758 2023-06-22T19:03:45 Z raysh07 Digital Circuit (IOI22_circuit) C++17
2 / 100
 493 ms 9736 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2e5 + 69;
const int mod = 1e9 + 2022;
vector <int> adj[N];
int n, m;
int w1[N], tot[N], ok[N], aa[N];
pair <int, int> seg[4 * N];
int lazy[4 * N];

void Build(int l, int r, int pos){
    if (l == r){
        seg[pos].first = aa[l];
        seg[pos].second = w1[l] * aa[l];
        lazy[pos] = 0;
        return;
    }
    
    int mid = (l + r)/2;
    Build(l, mid, pos*2);
    Build(mid + 1, r, pos*2 + 1);
    
    seg[pos].first = seg[pos * 2].first + seg[pos * 2 + 1].first;
    seg[pos].second = seg[pos * 2].second + seg[pos * 2 + 1].second;
}

void updlz(int l, int r, int pos){
    seg[pos].second = seg[pos].first - seg[pos].second;
    lazy[pos] = 0;
    if (l == r) return;
    lazy[pos * 2] ^= 1;
    lazy[pos * 2 + 1] ^= 1;
}

void upd(int l, int r, int pos, int ql, int qr){
    if (lazy[pos] != 0) updlz(l, r, pos);
    if (l >= ql && r <= qr){
        seg[pos].second = seg[pos].first - seg[pos].second;
        if (l == r) return;
        
        lazy[pos * 2] ^= 1;
        lazy[pos * 2 + 1] ^= 1;
        return;
    } else if (l > qr || r < ql){
        return;
    }
    
    int mid = (l + r)/2;
    upd(l, mid, pos*2, ql, qr);
    upd(mid + 1, r, pos*2 + 1, ql, qr);
    
    seg[pos].first = seg[pos * 2].first + seg[pos * 2 + 1].first;
    seg[pos].second = seg[pos * 2].second + seg[pos * 2 + 1].second;
}

int power(int x, int y){
    if (y==0) return 1;
    
    int v = power(x, y/2);
    v *= v; v %= mod;
    
    if (y & 1) return v * x % mod;
    else return v;
}

// void dfs(int u){
//     int cnt = 0;
//     for (int v : adj[u]){
//         dfs(v);
//         cnt++;
//     }
    
//     if (u >= n) return;
    
//     int curr = 1;
//     w1[u] = 0;
    
//     for (int v : adj[u]){
//         ok[v] = curr;
//         curr *= tot[v]; 
//         curr %= mod;
//     }
//     tot[u] = curr * cnt % mod;
//     curr = 1;
    
//     for (int i = adj[u].size() - 1; i >= 0; i--){
//         int v = adj[u][i];
//         ok[v] *= curr;
//         ok[v] %= mod;
//         curr *= tot[v];
//         curr %= mod;
//     }
    
//     for (int v : adj[u]){
//         w1[u] += w1[v] * ok[v] % mod;
//         w1[u] %= mod;
//     }
// }

void dfs2(int u){
    int cnt = 0;
    tot[u] = 1;
    for (int v : adj[u]){
        cnt++;
        dfs2(v);
        tot[u] *= tot[v];
        tot[u] %= mod;
    }
    
    if (cnt != 0)
    tot[u] *= cnt;
    tot[u] %= mod;
}

void dfs(int u){
    int curr = 1;
    for (int v : adj[u]){
        ok[v] = curr;
        curr *= tot[v];
        curr %= mod;
    }
    
    // tot[u] = curr;
    // if (cnt != 1) tot[u] *= cnt, tot[u] %= mod;
    
    reverse(adj[u].begin(), adj[u].end());
    curr = 1;
    for (int v : adj[u]){
        ok[v] *= curr; 
        ok[v] %= mod;
        ok[v] *= ok[u];
        ok[v] %= mod;
        curr *= tot[v];
        curr %= mod;
        
        dfs(v);
    }
}

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; i++){
        adj[p[i]].push_back(i);
    }
    
    // for (int i = n; i < n + m; i++){
    //     for (int j = n; j < n + m; j++){
    //         tot[j] = 1;
    //         if (j == i) w1[j] = 1;
    //         else w1[j] = 0;
    //     }
        
    //     dfs(0);
    //     aa[i] = w1[0];
    // }
    
    dfs2(0);
    
    // for (int i = 0; i < n + m; i++) cout << tot[i] << " ";
    // cout << "\n";
    ok[0] = 1;
    dfs(0);
    for (int i = n; i < n + m; i++) {
        aa[i] = ok[i];
       // cout << aa[i] << " ";
    }
  //  cout << "\n";
    
    for (int i = 0; i < m; i++){
        if (a[i] == 1)
        w1[i + n] = 1;
        else w1[i + n] = 0;
    }
    
    Build(n, n + m - 1, 1);
}

int32_t count_ways(int32_t l, int32_t r) {
    upd(n, n + m - 1, 1, l, r);
    
    int32_t ans = seg[1].second;
    
    return ans % mod;
}

// int32_t main(){
//     int32_t n, m; cin >> n >> m;
    
//     vector <int32_t> p(n + m), a(m);
//     for (auto &x : p) cin >> x;
//     for (auto &x : a) cin >> x;
//     init(n, m, p, a);
    
//     int q; cin >> q;
//     while(q--){
//         int32_t l, r;
//         cin >> l >> r;
//         cout << count_ways(l, r) << "\n";
//     }
//     return 0;
// }

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 5008 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 2 ms 5072 KB Output is correct
7 Correct 2 ms 5036 KB Output is correct
8 Correct 3 ms 5072 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 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-782332698'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 493 ms 9736 KB 1st lines differ - on the 1st token, expected: '431985922', found: '-747097920'
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 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-782332698'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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