oj.uz

Submission #812292

# Submission time Handle Problem Language Result Execution time Memory
812292 2023-08-07T08:14:15 Z BT21tata Digital Circuit (IOI22_circuit) C++17
18 / 100
 869 ms 13316 KB 
#include "circuit.h"
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
const ll MOD=1e9+2022;
const int N=2e5+5;

struct tree
{
    ll one, all, lazy;
}t[4*N];

int nw[N], cnt, old[N], n, m;
ll suff[N], prv=1, a[N];
vector<int>g[N];

void dfs(int v)
{
    if(!g[v].size()) return;
    old[cnt]=v;
    nw[v]=cnt++;
    for(int u : g[v])
        dfs(u);
}

void calc(int v, int p)
{
    if(!g[v].size())
    {
        a[v-n]=prv*suff[nw[p]+1];
        a[v-n]%=MOD;
        return;
    }
    
    for(int u : g[v])
        calc(u, v);
    
    prv*=g[v].size();
    prv%=MOD;
}

void build(int v, int l, int r, vector<int>&state)
{
    if(l==r)
    {
        if(state[l]) t[v]={a[l], a[l], 0};
        else t[v]={0, a[l], 0};
        return;
    }
    
    int mid=(l+r)>>1;
    build(v<<1, l, mid, state);
    build(v<<1|1, mid+1, r, state);

    t[v]={(t[v<<1].one+t[v<<1|1].one)%MOD, (t[v<<1].all+t[v<<1|1].all)%MOD, 0};
}

void push(int v, int l, int r)
{
    t[v].one=(t[v].all-t[v].one+MOD)%MOD;
    t[v].lazy=0;
    if(l!=r)
    {
        t[v<<1].lazy^=1;
        t[v<<1|1].lazy^=1;
    }
}

void update(int v, int l, int r, int tl, int tr)
{
    if(t[v].lazy) push(v, l, r);
    if(r<tl or tr<l) return;
    if(tl<=l and r<=tr)
    {
        t[v].lazy=1;
        push(v, l, r);
        return;
    }

    int mid=(l+r)>>1;
    update(v<<1, l, mid, tl, tr);
    update(v<<1|1, mid+1, r, tl, tr);

    t[v]={(t[v<<1].one+t[v<<1|1].one)%MOD, (t[v<<1].all+t[v<<1|1].all)%MOD, 0};
}

void init(int N, int M, vector<int> p, vector<int> state)
{
    n=N; m=M;
    for(int i=1; i<n+m; i++)
        g[p[i]].push_back(i);

    dfs(0);

    suff[n]=1;
    for(int i=n-1; i>=0; i--)
    {
        suff[i]=suff[i+1]*g[old[i]].size();
        suff[i]%=MOD;
    }

    calc(0, -1);

    build(1, 0, m-1, state);
}

int count_ways(int l, int r)
{
    update(1, 0, m-1, l-n, r-n);
    return t[1].one;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4932 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 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 2 ms 5072 KB Output is correct
8 Correct 2 ms 5020 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4932 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 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 2 ms 5072 KB Output is correct
8 Correct 2 ms 5020 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 2 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
15 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 9108 KB Output is correct
2 Correct 630 ms 13220 KB Output is correct
3 Correct 679 ms 13208 KB Output is correct
4 Correct 676 ms 13240 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 9108 KB Output is correct
2 Correct 630 ms 13220 KB Output is correct
3 Correct 679 ms 13208 KB Output is correct
4 Correct 676 ms 13240 KB Output is correct
5 Correct 623 ms 9116 KB Output is correct
6 Correct 704 ms 13204 KB Output is correct
7 Correct 869 ms 13280 KB Output is correct
8 Correct 610 ms 13316 KB Output is correct
9 Correct 219 ms 5200 KB Output is correct
10 Correct 734 ms 5456 KB Output is correct
11 Correct 817 ms 5456 KB Output is correct
12 Correct 688 ms 5456 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4932 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 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 2 ms 5072 KB Output is correct
8 Correct 2 ms 5020 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 2 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
15 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4932 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 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 2 ms 5072 KB Output is correct
8 Correct 2 ms 5020 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 2 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
15 Halted 0 ms 0 KB -