oj.uz

Submission #763741

# Submission time Handle Problem Language Result Execution time Memory
763741 2023-06-22T18:12:17 Z raysh07 Digital Circuit (IOI22_circuit) C++17
0 / 100
 3000 ms 7700 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], sub[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){
    sub[u] = 0;
    if (u >= n) sub[u] = 1;
    for (int v : adj[u]){
        dfs(v);
        sub[u] += sub[v];
    }
    
    if (u >= n) return;
    w1[u] = 0;
    for (int v : adj[u]){
        w1[u] += w1[v] * power(2, sub[u] - sub[v]);
        w1[u] %= 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;
    }
}

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

Subtask #1
0 / 2.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 7700 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 7700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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