oj.uz

Submission #812250

# Submission time Handle Problem Language Result Execution time Memory
812250 2023-08-07T08:00:44 Z BT21tata Digital Circuit (IOI22_circuit) C++17
18 / 100
 853 ms 13228 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, zero, 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], 0, 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].zero+t[v<<1|1].zero)%MOD, 0};
}

void push(int v, int l, int r)
{
    swap(t[v].zero, t[v].one);
    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].zero+t[v<<1|1].zero)%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 2 ms 4944 KB Output is correct
2 Correct 3 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 5008 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 5072 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 3 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 2 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 2 ms 4944 KB Output is correct
2 Correct 3 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 5008 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 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 3 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 2 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 459 ms 9040 KB Output is correct
2 Correct 792 ms 13192 KB Output is correct
3 Correct 780 ms 13192 KB Output is correct
4 Correct 641 ms 13228 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 9040 KB Output is correct
2 Correct 792 ms 13192 KB Output is correct
3 Correct 780 ms 13192 KB Output is correct
4 Correct 641 ms 13228 KB Output is correct
5 Correct 703 ms 9040 KB Output is correct
6 Correct 699 ms 13128 KB Output is correct
7 Correct 853 ms 13188 KB Output is correct
8 Correct 757 ms 13188 KB Output is correct
9 Correct 288 ms 5200 KB Output is correct
10 Correct 628 ms 5456 KB Output is correct
11 Correct 739 ms 5456 KB Output is correct
12 Correct 528 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 3 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 2 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 2 ms 4944 KB Output is correct
2 Correct 3 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 5008 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 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 3 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 2 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 2 ms 4944 KB Output is correct
2 Correct 3 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 5008 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 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 3 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 2 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
15 Halted 0 ms 0 KB -