oj.uz

Submission #628863

# Submission time Handle Problem Language Result Execution time Memory
628863 2022-08-13T18:41:36 Z welleyth Digital Circuit (IOI22_circuit) C++17
11 / 100
 3000 ms 12444 KB 
#include "circuit.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;

constexpr int NN = (int)2e5+111;
constexpr int md = (int)1e9+2022;
typedef long long ll;
int a[NN];
std::vector<int> g[NN];
ll dp[2][NN];
ll all[NN];
int p[NN];
int n,m;

void dfs(int v){
    if(g[v].empty())
        return;
    for(auto& to : g[v]){
        dfs(to);
    }
    int sz = g[v].size();
    for(int i = 1; i < (1 << sz); i++){
        int k = 1;
        for(int j = 0; j < sz; j++){
            k = (k * dp[i >> j & 1][g[v][j]]) % md;
        }
        dp[1][v] += __builtin_popcount(i) * k;
        dp[1][v] %= md;
    }
    all[v] = g[v].size();
    for(auto& to : g[v]){
        all[v] = (all[v] * all[to]) % md;
    }
    dp[0][v] = (all[v] - dp[1][v] + md) % md;
    return;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    p[0] = -1;
    for(int i = 1; i < N+M; i++){
        g[P[i]].push_back(i);
        p[i] = P[i];
    }
    for(int i = 0; i < M; i++){
        a[i+N] = A[i];
        dp[1][i+N] = A[i];
        dp[0][i+N] = A[i] ^ 1;
        all[i+N] = 1;
    }
    n = N;
    m = M;
    dfs(0);
    return;
}

void go(int v){
    if(v == -1)
        return;
//    cerr << "v = " << v << "\n";
    if(g[v].empty()){
        go(p[v]);
        return;
    }
    int sz = g[v].size();
    dp[1][v] = 0;
    dp[0][v] = 0;
    for(int i = 1; i < (1 << sz); i++){
        int k = 1;
        for(int j = 0; j < sz; j++){
            k = (k * dp[i >> j & 1][g[v][j]]) % md;
        }
        dp[1][v] += __builtin_popcount(i) * k % md;
        dp[1][v] %= md;
    }
    all[v] = g[v].size();
    for(auto& to : g[v]){
        all[v] = (all[v] * all[to]) % md;
    }
    dp[0][v] = (all[v] - dp[1][v] + md) % md;
    go(p[v]);
    return;
}

int count_ways(int L, int R) {
    for(int i = L; i <= R; i++){
        a[i] ^= 1;
        dp[1][i] ^= 1;
        dp[0][i] ^= 1;
        go(p[i]);
    }
//    dfs(0);
    return dp[1][0];
}
/**
3 4 3
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
3 6

1 2 1
-1 0 0
0 0
1 1

**/

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Execution timed out 3061 ms 5072 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 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 4 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 6 ms 5144 KB Output is correct
10 Correct 71 ms 5248 KB Output is correct
11 Correct 117 ms 5200 KB Output is correct
12 Correct 3 ms 5072 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Execution timed out 3061 ms 5072 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 8656 KB Output is correct
2 Correct 979 ms 12444 KB Output is correct
3 Correct 918 ms 12428 KB Output is correct
4 Correct 1020 ms 12420 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 8656 KB Output is correct
2 Correct 979 ms 12444 KB Output is correct
3 Correct 918 ms 12428 KB Output is correct
4 Correct 1020 ms 12420 KB Output is correct
5 Execution timed out 3016 ms 8656 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 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 4 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 6 ms 5144 KB Output is correct
10 Correct 71 ms 5248 KB Output is correct
11 Correct 117 ms 5200 KB Output is correct
12 Correct 3 ms 5072 KB Output is correct
13 Correct 620 ms 8656 KB Output is correct
14 Correct 979 ms 12444 KB Output is correct
15 Correct 918 ms 12428 KB Output is correct
16 Correct 1020 ms 12420 KB Output is correct
17 Execution timed out 3016 ms 8656 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Execution timed out 3061 ms 5072 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Execution timed out 3061 ms 5072 KB Time limit exceeded
4 Halted 0 ms 0 KB -