oj.uz

Submission #653499

# Submission time Handle Problem Language Result Execution time Memory
653499 2022-10-27T02:20:35 Z Lobo Digital Circuit (IOI22_circuit) C++17
2 / 100
 3000 ms 8196 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(int no, int l, int r, int L, int R) {
    flush(no,l,r);
    if(l > R || r < L) return;
    if(l >= L && r <= R) {
        lz[no] = 1;
        flush(no,l,r);
        return;
    }
    int 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];
    }
    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 5084 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 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 5072 KB Output is correct
3 Correct 22 ms 5072 KB Output is correct
4 Correct 28 ms 5072 KB Output is correct
5 Correct 28 ms 5080 KB Output is correct
6 Correct 1313 ms 5084 KB Output is correct
7 Correct 1574 ms 5116 KB Output is correct
8 Correct 1224 ms 5112 KB Output is correct
9 Correct 1869 ms 5132 KB Output is correct
10 Execution timed out 3066 ms 5200 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 5084 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 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 5072 KB Output is correct
11 Correct 22 ms 5072 KB Output is correct
12 Correct 28 ms 5072 KB Output is correct
13 Correct 28 ms 5080 KB Output is correct
14 Correct 1313 ms 5084 KB Output is correct
15 Correct 1574 ms 5116 KB Output is correct
16 Correct 1224 ms 5112 KB Output is correct
17 Correct 1869 ms 5132 KB Output is correct
18 Execution timed out 3066 ms 5200 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 3086 ms 8196 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 3086 ms 8196 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 5072 KB Output is correct
3 Correct 22 ms 5072 KB Output is correct
4 Correct 28 ms 5072 KB Output is correct
5 Correct 28 ms 5080 KB Output is correct
6 Correct 1313 ms 5084 KB Output is correct
7 Correct 1574 ms 5116 KB Output is correct
8 Correct 1224 ms 5112 KB Output is correct
9 Correct 1869 ms 5132 KB Output is correct
10 Execution timed out 3066 ms 5200 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 5084 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 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 5072 KB Output is correct
11 Correct 22 ms 5072 KB Output is correct
12 Correct 28 ms 5072 KB Output is correct
13 Correct 28 ms 5080 KB Output is correct
14 Correct 1313 ms 5084 KB Output is correct
15 Correct 1574 ms 5116 KB Output is correct
16 Correct 1224 ms 5112 KB Output is correct
17 Correct 1869 ms 5132 KB Output is correct
18 Execution timed out 3066 ms 5200 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 5084 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 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 5072 KB Output is correct
11 Correct 22 ms 5072 KB Output is correct
12 Correct 28 ms 5072 KB Output is correct
13 Correct 28 ms 5080 KB Output is correct
14 Correct 1313 ms 5084 KB Output is correct
15 Correct 1574 ms 5116 KB Output is correct
16 Correct 1224 ms 5112 KB Output is correct
17 Correct 1869 ms 5132 KB Output is correct
18 Execution timed out 3066 ms 5200 KB Time limit exceeded
19 Halted 0 ms 0 KB -