oj.uz

Submission #912713

# Submission time Handle Problem Language Result Execution time Memory
912713 2024-01-19T18:25:41 Z biank Digital Circuit (IOI22_circuit) C++17
11 / 100
 3000 ms 2097152 KB 
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll,ll> pll; 
#define ALL(x) x.begin(),x.end()
#define SIZE(x) (int)x.size()
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define fst first
#define snd second
#define pb push_back
const int MAXN = 2e5;
const int MOD = 1e9+2022;
vi s, adj[MAXN], p;
int n, m;
int dp[MAXN][2];
 
int mul(int x, int y) {
    return int(1LL*x*y%MOD);
}

void add(int &x, int y) {
    x+=y;
    if(x>=MOD) x-=MOD;
}
 
void compute_dp(int u) {
    int l=adj[u][0], r=adj[u][1];
    
    int aux = mul(dp[l][0], dp[r][1]);
    add(aux, mul(dp[l][1], dp[r][0]));
    dp[u][1] = dp[u][0] = aux;
    
    aux = mul(mul(2, dp[l][0]), dp[r][0]);
    add(dp[u][0], aux);
    
    aux = mul(mul(2, dp[l][1]), dp[r][1]);
    add(dp[u][1], aux);
}
 
void dfs(int u) {
    if(SIZE(adj[u])==0) {
        dp[u][s[u-n]] = 1;
        dp[u][!s[u-n]] = 0;
        return;
    }
    int l=adj[u][0], r=adj[u][1];
    dfs(l), dfs(r);
    compute_dp(u);
}
 
void init(int N, int M, vi P, vi A) {
    s=A, n=N, m=M, p=P;
    forsn(i,1,n+m) adj[P[i]].pb(i);
    dfs(0);
}

void update(int u) {
    dp[u][0]^=1, dp[u][1]^=1;
    u=p[u];
    while(u!=-1) {
        compute_dp(u);
        u=p[u];
    }
}
 
int count_ways(int L, int R) {
    forsn(i,L,R+1) {
        s[i-n]^=1;
        update(i);
    }
    return dp[0][1];
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Runtime error 1790 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 3 ms 6488 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Correct 3 ms 6488 KB Output is correct
6 Correct 3 ms 6488 KB Output is correct
7 Correct 3 ms 6488 KB Output is correct
8 Correct 4 ms 6488 KB Output is correct
9 Correct 3 ms 6488 KB Output is correct
10 Correct 22 ms 6488 KB Output is correct
11 Correct 40 ms 6488 KB Output is correct
12 Correct 3 ms 6488 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Runtime error 1790 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 8788 KB Output is correct
2 Correct 590 ms 11120 KB Output is correct
3 Correct 610 ms 10896 KB Output is correct
4 Correct 609 ms 10864 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 8788 KB Output is correct
2 Correct 590 ms 11120 KB Output is correct
3 Correct 610 ms 10896 KB Output is correct
4 Correct 609 ms 10864 KB Output is correct
5 Execution timed out 3011 ms 8712 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 3 ms 6488 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Correct 3 ms 6488 KB Output is correct
6 Correct 3 ms 6488 KB Output is correct
7 Correct 3 ms 6488 KB Output is correct
8 Correct 4 ms 6488 KB Output is correct
9 Correct 3 ms 6488 KB Output is correct
10 Correct 22 ms 6488 KB Output is correct
11 Correct 40 ms 6488 KB Output is correct
12 Correct 3 ms 6488 KB Output is correct
13 Correct 408 ms 8788 KB Output is correct
14 Correct 590 ms 11120 KB Output is correct
15 Correct 610 ms 10896 KB Output is correct
16 Correct 609 ms 10864 KB Output is correct
17 Execution timed out 3011 ms 8712 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Runtime error 1790 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Runtime error 1790 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -