oj.uz

Submission #653498

# Submission time Handle Problem Language Result Execution time Memory
653498 2022-10-27T02:18:46 Z Lobo Digital Circuit (IOI22_circuit) C++17
2 / 100
 3000 ms 8844 KB 
#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;
const int mod = 1000002022;
int n, m, p[maxn], a[maxn];
vector<int> g[maxn];
int c[maxn], pw2[maxn], prd[maxn];
int32_t tr0[4*maxn],tr1[4*maxn],lz[4*maxn];

void build(int no, int l, int r) {
    if(l == r) {
        tr0[no] = (a[l-n] == 0)*prd[l];
        tr1[no] = (a[l-n] == 1)*prd[l];
        return;
    }
    int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
    build(f1,l,mid);
    build(f2,mid+1,r);
    tr0[no] = (tr0[f1]+tr0[f2])%mod;
    tr1[no] = (tr1[f1]+tr1[f2])%mod;
}

void flush(int no, int l, int r) {
    if(lz[no] == 0) return;
    swap(tr0[no],tr1[no]);
    if(l != r) {
        int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
        lz[f1]^= 1;
        lz[f2]^= 1;
    }
    lz[no] = 0;
}

void att(int32_t no, int32_t l, int32_t r, int32_t L, int32_t R) {
    flush(no,l,r);
    if(l > R || r < L) return;
    if(l >= L && r <= R) {
        lz[no] = 1;
        flush(no,l,r);
        return;
    }
    int32_t f1=2*no,f2=2*no+1,mid=(l+r)>>1;
    att(f1,l,mid,L,R);
    att(f2,mid+1,r,L,R);
    tr0[no] = (tr0[f1]+tr0[f2])%mod;
    tr1[no] = (tr1[f1]+tr1[f2])%mod;
}

void dfssz(int u) {
    c[u] = g[u].size();
    if(u >= n) c[u] = 1;
    if(u >= n) return;
    for(auto v : g[u]) {
        dfssz(v);
        c[u] = c[u]*c[v]%mod;
    }
}

void dfs(int u) {
    vector<int> pf(g[u].size()+1), sf(g[u].size()+1);

    for(int i = 0; i < (int) g[u].size(); i++) {
        int v = g[u][i];
        pf[i] = c[v];
        if(i!=0) pf[i] = pf[i]*pf[i-1]%mod;
    }
    for(int i = (int) g[u].size()-1; i >= 0; i--) {
        int v = g[u][i];
        sf[i] = c[v];
        if(i != (int) g[u].size()-1) sf[i] = sf[i]*sf[i+1]%mod;
    }

    for(int i = 0; i < (int) g[u].size(); i++) {
        int v = g[u][i];
        prd[v] = prd[u];
        if(i != 0) prd[v] = prd[v]*pf[i-1]%mod;
        if(i != (int) g[u].size()-1) prd[v] = prd[v]*sf[i+1]%mod;
        dfs(v);
    }

    for(auto v : g[u]) {
        dfs(v);
    }
}

int ans = 0;
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++) {
        p[i] = P[i];
        g[p[i]].pb(i);
    }
    for(int i = 0; i < m; i++) {
        a[i] = A[i];
    }
    pw2[0] = 1;
    for(int i = 1; i <= n+m; i++) {
        pw2[i] = pw2[i-1]*2%mod;
    }
    dfssz(0);
    prd[0] = 1;
    dfs(0);
    build(1,n,n+m-1);
}
int32_t count_ways(int32_t L, int32_t R) {
    att(1,n,n+m-1,L,R);
    return tr1[1];
}

Compilation message

circuit.cpp: In function 'void flush(long long int, long long int, long long int)':
circuit.cpp:37:31: warning: unused variable 'mid' [-Wunused-variable]
   37 |         int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
      |                               ^~~

Subtask #1
2.0 / 2.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 5156 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5160 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 8 ms 5064 KB Output is correct
3 Correct 22 ms 5092 KB Output is correct
4 Correct 24 ms 5096 KB Output is correct
5 Correct 20 ms 5072 KB Output is correct
6 Correct 1295 ms 5104 KB Output is correct
7 Correct 1563 ms 5144 KB Output is correct
8 Correct 1127 ms 5140 KB Output is correct
9 Correct 1822 ms 5144 KB Output is correct
10 Execution timed out 3084 ms 5328 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 9.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 5156 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5160 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 8 ms 5064 KB Output is correct
11 Correct 22 ms 5092 KB Output is correct
12 Correct 24 ms 5096 KB Output is correct
13 Correct 20 ms 5072 KB Output is correct
14 Correct 1295 ms 5104 KB Output is correct
15 Correct 1563 ms 5144 KB Output is correct
16 Correct 1127 ms 5140 KB Output is correct
17 Correct 1822 ms 5144 KB Output is correct
18 Execution timed out 3084 ms 5328 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3023 ms 8844 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 3023 ms 8844 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 8 ms 5064 KB Output is correct
3 Correct 22 ms 5092 KB Output is correct
4 Correct 24 ms 5096 KB Output is correct
5 Correct 20 ms 5072 KB Output is correct
6 Correct 1295 ms 5104 KB Output is correct
7 Correct 1563 ms 5144 KB Output is correct
8 Correct 1127 ms 5140 KB Output is correct
9 Correct 1822 ms 5144 KB Output is correct
10 Execution timed out 3084 ms 5328 KB Time limit exceeded
11 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 3 ms 4944 KB Output is correct
3 Correct 3 ms 5156 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5160 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 8 ms 5064 KB Output is correct
11 Correct 22 ms 5092 KB Output is correct
12 Correct 24 ms 5096 KB Output is correct
13 Correct 20 ms 5072 KB Output is correct
14 Correct 1295 ms 5104 KB Output is correct
15 Correct 1563 ms 5144 KB Output is correct
16 Correct 1127 ms 5140 KB Output is correct
17 Correct 1822 ms 5144 KB Output is correct
18 Execution timed out 3084 ms 5328 KB Time limit exceeded
19 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 3 ms 4944 KB Output is correct
3 Correct 3 ms 5156 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5160 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 8 ms 5064 KB Output is correct
11 Correct 22 ms 5092 KB Output is correct
12 Correct 24 ms 5096 KB Output is correct
13 Correct 20 ms 5072 KB Output is correct
14 Correct 1295 ms 5104 KB Output is correct
15 Correct 1563 ms 5144 KB Output is correct
16 Correct 1127 ms 5140 KB Output is correct
17 Correct 1822 ms 5144 KB Output is correct
18 Execution timed out 3084 ms 5328 KB Time limit exceeded
19 Halted 0 ms 0 KB -