oj.uz

Submission #745268

# Submission time Handle Problem Language Result Execution time Memory
745268 2023-05-19T16:48:20 Z doowey Digital Circuit (IOI22_circuit) C++17
18 / 100
 3000 ms 7044 KB 
#include <bits/stdc++.h>
#include "circuit.h"

using namespace std;

typedef long long ll;

const int N = (int)2e5 + 10;
const int MOD = (int)1e9 + 2022;
vector<int> T[N];
int dp[N][2];

int add(int x, int y){
    x += y;
    if(x >= MOD) x -= MOD;
    else if(x < 0) x += MOD;
    return x;
}

int mult(int x, int y){
    return (x * 1ll * y) % MOD;
}

void dfs(int u){
    if(T[u].empty()) return;
    int S = 0;
    int W = 1;
    dp[u][0] = 1;
    for(auto x : T[u]){
        dfs(x);

        S = mult(S, add(dp[x][0], dp[x][1]));
        S = add(S, mult(W, dp[x][1]));
        W = mult(W, add(dp[x][0], dp[x][1]));
        dp[u][0] = mult(dp[u][0], add(dp[x][0], dp[x][1]));
    }
    dp[u][1] = S;
    dp[u][0] = mult(dp[u][0], (int)T[u].size());
    dp[u][0] = add(dp[u][0], -dp[u][1]);
}

int n, m;

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 ++ ){
        T[P[i]].push_back(i);
    }
    for(int i = 0 ; i < m ; i ++ ){
        if(A[i] == 0){
            dp[i + n][0] = 1;
            dp[i + n][1] = 0;
        }
        else{
            dp[i + n][0] = 0;
            dp[i + n][1] = 1;
        }
    }
}

int count_ways(int li, int ri) {
    for(int i = li ; i <= ri ; i ++ ){
        swap(dp[i][0], dp[i][1]);
    }
    dfs(0);
    return dp[0][1];
}

Subtask #1
2.0 / 2.0

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

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 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 4 ms 4992 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 3 ms 5072 KB Output is correct
11 Correct 3 ms 5072 KB Output is correct
12 Correct 3 ms 4944 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5000 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 3 ms 4944 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 3 ms 4944 KB Output is correct
12 Correct 3 ms 4944 KB Output is correct
13 Correct 3 ms 4944 KB Output is correct
14 Correct 3 ms 4944 KB Output is correct
15 Correct 3 ms 4944 KB Output is correct
16 Correct 4 ms 4992 KB Output is correct
17 Correct 3 ms 4944 KB Output is correct
18 Correct 3 ms 5072 KB Output is correct
19 Correct 3 ms 5072 KB Output is correct
20 Correct 3 ms 4944 KB Output is correct
21 Correct 3 ms 4944 KB Output is correct
22 Correct 4 ms 4944 KB Output is correct
23 Correct 3 ms 4944 KB Output is correct
24 Correct 3 ms 4944 KB Output is correct
25 Correct 3 ms 4944 KB Output is correct
26 Correct 4 ms 4944 KB Output is correct
27 Correct 3 ms 4944 KB Output is correct
28 Correct 3 ms 4944 KB Output is correct
29 Correct 3 ms 4944 KB Output is correct
30 Correct 3 ms 4944 KB Output is correct
31 Correct 3 ms 5072 KB Output is correct
32 Correct 3 ms 4944 KB Output is correct
33 Correct 3 ms 4944 KB Output is correct
34 Correct 3 ms 4944 KB Output is correct
35 Correct 3 ms 4944 KB Output is correct
36 Correct 4 ms 5072 KB Output is correct
37 Correct 3 ms 5072 KB Output is correct
38 Correct 3 ms 5072 KB Output is correct
39 Correct 3 ms 4944 KB Output is correct
40 Correct 3 ms 4944 KB Output is correct
41 Correct 3 ms 4944 KB Output is correct
42 Correct 3 ms 4944 KB Output is correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 7044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 7044 KB Time limit exceeded
2 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 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 4 ms 4992 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 3 ms 5072 KB Output is correct
11 Correct 3 ms 5072 KB Output is correct
12 Correct 3 ms 4944 KB Output is correct
13 Execution timed out 3050 ms 7044 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5000 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 3 ms 4944 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 3 ms 4944 KB Output is correct
12 Correct 3 ms 4944 KB Output is correct
13 Correct 3 ms 4944 KB Output is correct
14 Correct 3 ms 4944 KB Output is correct
15 Correct 3 ms 4944 KB Output is correct
16 Correct 4 ms 4992 KB Output is correct
17 Correct 3 ms 4944 KB Output is correct
18 Correct 3 ms 5072 KB Output is correct
19 Correct 3 ms 5072 KB Output is correct
20 Correct 3 ms 4944 KB Output is correct
21 Correct 3 ms 4944 KB Output is correct
22 Correct 4 ms 4944 KB Output is correct
23 Correct 3 ms 4944 KB Output is correct
24 Correct 3 ms 4944 KB Output is correct
25 Correct 3 ms 4944 KB Output is correct
26 Correct 4 ms 4944 KB Output is correct
27 Correct 3 ms 4944 KB Output is correct
28 Correct 3 ms 4944 KB Output is correct
29 Correct 3 ms 4944 KB Output is correct
30 Correct 3 ms 4944 KB Output is correct
31 Correct 3 ms 5072 KB Output is correct
32 Correct 3 ms 4944 KB Output is correct
33 Correct 3 ms 4944 KB Output is correct
34 Correct 3 ms 4944 KB Output is correct
35 Correct 3 ms 4944 KB Output is correct
36 Correct 4 ms 5072 KB Output is correct
37 Correct 3 ms 5072 KB Output is correct
38 Correct 3 ms 5072 KB Output is correct
39 Correct 3 ms 4944 KB Output is correct
40 Correct 3 ms 4944 KB Output is correct
41 Correct 3 ms 4944 KB Output is correct
42 Correct 3 ms 4944 KB Output is correct
43 Execution timed out 3041 ms 5072 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5000 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 3 ms 4944 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 3 ms 4944 KB Output is correct
12 Correct 3 ms 4944 KB Output is correct
13 Correct 3 ms 4944 KB Output is correct
14 Correct 3 ms 4944 KB Output is correct
15 Correct 3 ms 4944 KB Output is correct
16 Correct 4 ms 4992 KB Output is correct
17 Correct 3 ms 4944 KB Output is correct
18 Correct 3 ms 5072 KB Output is correct
19 Correct 3 ms 5072 KB Output is correct
20 Correct 3 ms 4944 KB Output is correct
21 Correct 3 ms 4944 KB Output is correct
22 Correct 4 ms 4944 KB Output is correct
23 Correct 3 ms 4944 KB Output is correct
24 Correct 3 ms 4944 KB Output is correct
25 Correct 3 ms 4944 KB Output is correct
26 Correct 4 ms 4944 KB Output is correct
27 Correct 3 ms 4944 KB Output is correct
28 Correct 3 ms 4944 KB Output is correct
29 Correct 3 ms 4944 KB Output is correct
30 Correct 3 ms 4944 KB Output is correct
31 Correct 3 ms 5072 KB Output is correct
32 Correct 3 ms 4944 KB Output is correct
33 Correct 3 ms 4944 KB Output is correct
34 Correct 3 ms 4944 KB Output is correct
35 Correct 3 ms 4944 KB Output is correct
36 Correct 4 ms 5072 KB Output is correct
37 Correct 3 ms 5072 KB Output is correct
38 Correct 3 ms 5072 KB Output is correct
39 Correct 3 ms 4944 KB Output is correct
40 Correct 3 ms 4944 KB Output is correct
41 Correct 3 ms 4944 KB Output is correct
42 Correct 3 ms 4944 KB Output is correct
43 Execution timed out 3050 ms 7044 KB Time limit exceeded
44 Halted 0 ms 0 KB -