Submission #763743

#	Time	Username	Problem	Language	Result	Execution time	Memory
763743		raysh07	Digital Circuit (IOI22_circuit)	C++17	0 / 100	3098 ms	8288 KiB

circuit

#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];

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

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 = 0; i < m; i++){
        if (a[i] == 1)
        w1[i + n] = 1;
        tot[i + n] = 1;
    }
}

int32_t count_ways(int32_t l, int32_t r) {
    for (int i = l + n; i <= r + n; i++){
        w1[i] ^= 1;
    }
    
    dfs(0);
    
    return (int32_t) w1[0];
}

// int main(){
//     int32_t n, m; cin >> n >> m;
    
//     vector <int32_t> p, a;
//     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: 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